Tanky WooRSS

《算法导论》学习总结 --- 2.第一章 && 第二章 && 第三章

09 Apr 2011
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

建议先看看前言:http://www.wutianqi.com/?p=2298

前三章基本没什么内容,所以合在一起总结。

第一章:

讲了算法(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个元素的子序列。

这个是分治法的精髓:

[![mergesort](https://images.tankywoo.com/oldblog/2011/04/mergesort_thumb.jpg)](https://images.tankywoo.com/oldblog/2011/04/mergesort.jpg)

其实理解起来很简单,有没有发现和二叉树的后序遍历类似。

第三章:

一般而言,我们研究的是算法的渐进意义。我在这里把渐进确界,渐进上界,渐进下界的三个符号的定义放在了一起:

jianjinfuhao书上的图3-1也非常给力:

jianjin 

这一章全部很重要。可以先记住,然后在后面的章节通过实践来掌握

Tanky Woo 标签: 算法导论算法分析渐进效率