初学算法

作者:bibodeng 发布于:2012-3-14 21:23 Wednesday 分类:技术交流

这个学期才刚刚接触算法,之前对于算法总是觉得高高在上,可望不可及。现实真的是这样,算法真的很难学哪,所以自认很菜鸟的我从来都很少写技术性的文章,实在是有点过意不去。不过这个学期的老师真的是非常好,能够和我们打成一片,让我对算法兴趣大增,感觉掌握了这门技术就十分的了不起。

 

从大一就开始看很多文章,包括李开复的《算法很重要》等等,于是在我的心目中就有了一个信念:算法很重要,我要学好算法。但是一直以来都在忙着其它“技术”,譬如学习编程语言,玩玩单片机啦,总之很“花心”。真正的基础技术——数据结构和算法却没有怎么注重。大二上才学的数据结构,也算认真听了,也挺有收获的,但是一到大二下的算法课我就懵了。特别是刚接触分治和递归,在动态规划这里纠缠,借了一本《算法之道》来看,写得非常好,但是我要很久才能进入状态从而理解其中的原理。我甚至怀疑是否是自己太笨3。

 

初初接触算法,就有一种特别强烈的想要实现它的感觉。看的时候总是会忽略大大小小的细节,然后在写的时候,到处出错。所以说,看懂了、读懂了都是屁话,只有实现了一遍而且有深刻领悟了才能说会了。许许多多的牛人都曾经说自己青涩的时候是怎么学习编程的——都是敲代码敲出来的,就算是抄也能锻炼手感。这几周只学了一章 分治和递归,就已经有许许多多的名堂了,什么归并排序、斐波那契、阿克曼函数等等全部出来了,这些初级问题当然是基本功,但是接下来的东西就比较有意思了:动态规划,这个东西用我自己的话来描述就是将复杂的问题分解成多个递归子问题解决的,这些小问题可以有重复,然后就需要我们找到一种方案(从底向上),使得怎样安排会最优,而这里的关系也是一步步的影响的(不知道理解的对不对,好模糊)——随机应变。好啰嗦呀,一步步的判断到底要走哪条路,当然要进行精细的计算了。虽然对它的理解非常地模糊,却使我想起来了project euler里面的一道题目,就是在一个三角形数堆找从上到下的和最小的路径,很显然就是利用动态规划的方法,当时是每一层的和进行比对,找最小的,如此直到最后(很显然是从底向上的构建过程)。

 

今天做的一个非常有趣的矩阵的连乘就是利用动态规划,因为矩阵的乘法可以结合但是不能交换,而且不同的结合计算次数会不一样。比如一个 2*3 矩阵A、一个3*2矩阵B 还有一个 2*4的矩阵C,也许班里还有少数童鞋还不知道怎样计算乘法次数(一开始我也不知道),举最简单的例子 A*B  那么得到的是一个 2*2的矩阵,而根据矩阵乘法的定义,可知要算出一个位置上的数都要计算3次乘法,故而计算乘法的次数就是 2*2*3,其实就是 行等于列那个数只乘一次即2*3*2。这样计算一下(AB)C 的计算次数,首先计算AB,前面已经得到结果了 2*3*2,得到一个2*2新矩阵,再和2*4矩阵相乘,要计算2*2*4。故而总共要计算 2*3*2+2*2*4 = 28次。然后计算一下 A(BC),先算BC,得到3*4新矩阵,再算 A [新矩阵],同理得到乘法次数3*2*4 +  2*3*4 = 48 ,两种方式相差了好多呀,真的是不可思议。故而要找到最佳的方法来结合,老师教会我们怎样使用方格来计算,每次这个东西都能解决动态规划的问题,真的是神奇,今天没有讲编程实现,不过一定会有一些if else之类的语句。

我是那张简单的会一点,复杂的我不会的人,但是为了牛逼的梦想,也只能老老实实地学习算法。

 

学算法是必须经得起考验的,算法是一种技术,一开始可能需要记忆,当这些深层次的思想进入我们的编程习惯中后,那么编起来将会得心应手。多跟老师学,学会一些经典的算法,了解它的来龙去脉,能够理解整个思路,找一本《算法导论》或者是TAOCP(假如能够啃的下的话),慢慢地学习这门技巧。

 

by bibodeng  2012-03-14

标签: 算法 编程 耐心

评论:

87737868
2012-03-15 10:50
字符间距可不可以改一下,要不然这么多字挤在一起看一起有点累
bibo-果冻
2012-03-16 21:44
@87737868:额好的,我会注意的
bibo-果冻
2012-03-16 21:47
@87737868:貌似改不了了,不好意思了

发表评论:

Powered by emlog 京ICP备16017775