算法的魅力

作者:bibodeng 发布于:2012-3-29 11:58 Thursday 分类:技术交流

正儿八经开始学算法了,没有学习算法之前,总觉得编程就是敲代码,知道怎样使用语言就行了,学习了算法之后,才知道这玩意大有用处,而且和数学有非常紧密的联系。虽然我数学不太好,但是我对数学有一种天生的好感,因为它们总是给人带来一种惊艳感。或许是小时候并不害怕数学的缘故吧,于是勉强坚持一下,老师所讲的那些动态规划、贪心算法居然能听懂了。但是看起《TAOCP》却是真正地无所适从,随时都有一种想要扔下书去干别的的感觉,而碰到容易的时候、自己能够理解就会非常地开心。

 

算法这种东西,的的确确需要很大的数学功底。我数学功底不好,该怎么拌?我就一行行照着敲代码,敲到我理解整个过程为止。或者对于我的“成果”(敲出来的代码)一行行进行调试,调试一遍就理解程序的基本原理了,但是自己还是写不出来。当然碰到各种递归,分治,调试的时候就超级没有耐心了,跳跃太频繁,人脑是难以接受的。比如一个quick sort ,先来一个partition,然后就递归解决前半部分和后半部分。真的是神奇,同样是排序算法,有的算法(快排)天生就比另外一些算法(冒泡、插入)更快,当然并不能一概而论,各种算法都有自己的局限以及长处。就像数据结构里面一样,顺序表和链式表都有各自的优点,但是也有各自的缺点,只有因时而异,因地制宜才能发挥它们最大的功效。算法也是一样,insert sort在样本少的时候是非常方便的,代码也少,适合那些顺序差不多和目的顺序相同的样本空间。而上述情况对于快排来说就是厄运的到来了,因为它们的思想完全不同,有序情况对快排来说是最糟糕的了,因为要partition打乱了,跳跃性太强,需要再继续排。

 

关于排序算法,记得还收藏过了一个排序的全集歌舞,用舞蹈的形式来展示排序的原理,比较容易懂。链接在这里。很多书上说计算机的世界里面很多需要排序的东西,而排序算法,便成了我们这堆初出茅庐的rookie们的必经之路。一大堆的排序算法,估计是各IT公司面试时最常考的东西,以前看的《疯狂的程序员》绝影最常被考的就是冒泡排序。而今天,对自己的要求当然不仅仅是能写几个排序,而更是要学会设计算法的本领,提高我们的产能,到时候产出自然就大了。前几天,搭车去本部参加ACM的初赛,居然很简单的问题想不出来,怪的就是没有算法的素养,对于题目的分析,解构,以及建模的能力不够,用惯了蛮力破解,却吃尽苦头编出一个超出时间要求的算法,好的算法往往需要一些基本功:递归、动态规划等的时候,就不知道从何处下手。结果可想而知——铩羽而归。当然,这也只是现阶段的情况而已,随着算法课程的推进,我们还是能够比较系统地接触各种算法,从而养成良好的算法素养,到时候就更轻松了。

 

今天读到一篇hack news说一个音乐生,跟着一个老师学才两年就大学毕业了,一个人真的可以学得很快,质的飞跃也往往只是需要半年的时间而已。而如果遇到了适合自己胃口的老师讲课,那么效率便会大大提高。我们于平常的学习中浪费了太多的时间,时间的确像海绵,但是挤出来的都浪费在别处去了。所以更难能可贵的是合理地管理自己,把重要知识掌握了,或者开辟一个大的时间内存,用于高效地运行一个“作业”。计算机能够分时、能够多进程、多线程,虽然从宏观上来讲,我们也是可以多进程的,但是就一个较短的时间段来说,我们还是应当高效地利用时间来学习重要的课程——数据结构和算法。也许读完了《算法导论》就可以很快上道了,要是能硬着头皮把《TAOCP》读完了,也就算得上是学有所成了。对于算法学习,很有必要给自己一个时间范围,给自己一个原则:“真的弄懂学习的算法,并在恰当的时候能够用上”。而且,越来越感觉到代码给人的直观性,敲过之后印象会更深刻。什么听懂了,看懂了,都是屁话,只有拉出来能够自己随手写一个才是真正的懂了。

 

以一个很惊奇的结果做结尾,做为启示:世界上的事物并非无缘无故的,而是有着千丝万缕的联系,而这种联系又是如此的精妙。就在你认为是毫无联系的情况下,有人发现了奇妙的联系。

 

project euler 052:找出一个数x,这个数的1、2、3、4、5、6倍都是由相同的一些数字组成,而且位数相同,求出这个数x。

 

咋一看,就是用Bruce 方法来破解,去试一试这些所有可能的结果。我苦逼了半天,辛辛苦苦地写出十几二十行代码,求得了正确的结果,可是看到反馈的第一条就是,这个人压根没有用计算机,就算得了结果,我十分地惊讶。

 

这个人说 1/7 = 0.142857... 而2*142857 = 285714; 3*142857 = 428571 ;4*142857 =571428 ;5*142857=  714285;6*142857=857142 真的是非常神奇!! 而7*142857 =999999

 

你现在你敢说这些数位和6是没关系的了吗?毕竟6和7有很大关系。而这之间的关系到底有多么深层呢,本质又是什么呢?这估计要去问群论的数学家了吧!

 

从中我悟到一个道理,那就是,算法要充分利用事物之间的联系:联系说不定就隐藏在表象的深层,充分利用联系的算法才是好的算法。

标签: 算法 编程 TAOCP

发表评论:

Powered by emlog 京ICP备16017775