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

建议先看看前言: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

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

第三章:

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

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

jianjin 

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

Tanky Woo 标签:

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《《算法导论》学习总结 — 2.第一章 && 第二章 && 第三章》有15个想法

  1. 我好想看啊!!!
    刚买了算导!!!
    可惜不能看!!!
    万恶的高考!!!
    准备以后看!!!
    学过微积分、线性代数,没学过概率论、离散数学,能读得了么?

    1. 呵呵,安心的看吧,大概要了解一些基础的高数,现代,离散,概率论知识吧。至于其他数学专业学的,比如组合数学,和算法就没区别了。。。

    2. 高考以后再说吧,上个好大学还是很重要的,毕竟NB的人多了,你也就NB了
      个人觉得学算法,不先学那一堆数学也能学得懂,不懂的地方Google一下就行了
      当然数学素养好的人,在算法方面的能力会比一般人强

    3. 还是学完概率和离散再看算导好了,好遥远的事。。。
      高考要悲剧,我就数学好,其他科巨差,尤其是语文,看了就想吐,克服不了唉~

发表评论

电子邮件地址不会被公开。 必填项已用*标注