上一篇:http://www.cppblog.com/tanky-woo/archive/2011/04/09/143794.html
前三章基本没什么内容,所以合在一起总结。
第一章:
讲了算法(algorithm)的基本概念,以及算法的作用。(这些可以看书)
用个人的话来讲,你可以把算法当做一个解决问题的方法,就像数学里的各种公式一样,你也可以把他们认为是一种算法。算法无处不在,而且算法必须存在,否则我们的生活都将变得缓慢,迟钝。
举个例子:我们平时出去游玩时,要事先查好路线,这时就可以用百度地图搜索从A地到B地的路线,地图上会给出最快的乘车路线,这些路线是怎么给出来的,就是用了最短路的算法,关于最短路的算法有很多,比如Dijkstra, Bellman, Floyd, SPFA等等,当然还有好多我不知道,但是通过这可以看出,算法可以让我们的生活变得更有效率。
当然,第一章也可以认为是给大家鼓气的一章,让大家发现算法的魅力,算法的强悍。大家都来爱上算法吧!
第二章:
本书的算法都是用伪代码写的,伪代码读起来很简单,它省去了无关的细节,着重考虑算法的整体。
2.1节讲的是插入排序(Insertion Sort),这个很简单,也可以认为是最基本的排序算法。
(P11)需要好好的记住,一般一本书中都会写一些事先的约定,以方便大家阅读。本书也不例外,这些约定都是关于伪代码的,为了更好的阅读并理解伪代码,所以这些约定要记住了!
2.2节讲的是算法的分析。算法分析是指对一个算法所需要的资源进行预测。在(P13)讲到了"运行时间"和"输入规模"的概念。一个程序的运行时间可以表示为一个输入规模的函数。一般算法所需的时间与输入规模是同步增长的,而且对于不同的输入序列,其运行时间也可能不同。(P14~15的算法运行时间分析要好好看看)。
2.3节讲的是分治法。
分治策略:将原问题划分成n个规模较小而结构与原问题相似的子问题;递归的解决这些子问题,然后再合并其结果,就得到原问题的解。
分治策略的三步骤(P17):分解(Divide),解决(Conquer),合并(Combine)。
合并排序算法就是利用了分治策略,将n个元素分成各含n/2个元素的子序列。
这个是分治法的精髓:
其实理解起来很简单,有没有发现和二叉树的后序遍历类似。
第三章:
一般而言,我们研究的是算法的渐进意义。我在这里把渐进确界,渐进上界,渐进下界的三个符号的定义放在了一起:
书上的图3-1也非常给力:
这一章全部很重要。可以先记住,然后在后面的章节通过实践来掌握
Tanky Woo 标签:
算法导论,
算法分析,
渐进效率
posted on 2011-04-10 09:53
Tanky Woo 阅读(2858)
评论(4) 编辑 收藏 引用