第一讲算法基础

1、第一章第一章 算法及基础知识算法及基础知识徐克奇 教材 算法设计与分析算法设计与分析王秋芬、吕聪颖等编著王秋芬、吕聪颖等编著 清华大学出版社清华大学出版社 2011年年8月月 参考教材参考教材 1.算法设计与分析算法设计与分析（第二版）王晓东编著（第二版）王晓东编著 清华大学出版社清华大学出版社 2008年年1月月 2. 算法设计与分析算法设计与分析c+语言描述语言描述陈慧南编著陈慧南编著 电子工业出版社电子工业出版社 2006年年5月月 算法概论算法概论(注释版注释版). Sanjoy Dasgupta等著，钱等著，钱枫等注释，机械工业出版社，枫等注释，机械工业出版社，2009 算法导论算法

2、导论（第二版（第二版 影印版）影印版）(美美) Corrmen. T. H. 北京：高等教育出版社，北京：高等教育出版社，20025主要内容 第1章算法及基础知识 第2章贪心法 第3章分治法 第4章动态规划 第5章搜索法 第6章随机化算法 第7章 线性规划问题 第8章 数论算法及计算几何算法 第9章 NP完全理论 为什么要学习算法？为什么要学习算法？ 算法是计算机科学的基石。算法是计算机科学的基石。没有算法，计算机程没有算法，计算机程序将不复存在序将不复存在 学习算法可以提高人们的分析能力。学习算法可以提高人们的分析能力。 算法可以看作是解决问题的一类特殊方法算法可以看作是解决问题的一类特殊方

3、法它它虽非问题的答案，但它是经过准确定义的，用来虽非问题的答案，但它是经过准确定义的，用来获得答案的过程。获得答案的过程。 无论是否涉及计算机，特定的算法设计技术都能无论是否涉及计算机，特定的算法设计技术都能看作是问题求解的有效策略。看作是问题求解的有效策略。 算法的魅力：算法的魅力：思考思考 程序程序=算法算法+数据结构数据结构 算法让我们上一个更高的台阶算法让我们上一个更高的台阶一个皇室数学挑战问题(1202)假设兔子出生一个月后能繁殖，以后每月产一个孩子，一直下去直到永远。从一个兔子开始，问n个月后有多少个兔子？Leonardo Fibonacci1170-1250兔子的繁殖成熟不成熟初

4、始一个月二个月三个月四个月五个月兔子出生一个月后能繁殖，以后每月产一个孩子，一直下去。设Fn是n个月时兔子的数量F1 = 1F2 = 1Fn = Fn-1 + Fn-2Fibonacci numbers:1, 1, 2, 3, 5, 8, 13, 21,34, 55, 89, 数量增长非常快: F30 106 !事实上, Fn 20.694n 1.6n, 指数级增长.可以证明 (3/2)nFn T(n-1) + T(n-2)但是 Fn = Fn-1 + Fn-2. 因此 T(n) Fn 指数级时间. 这有多糟糕?例. 计算 F200 大概需要 2140 个运算.在一个快速计算机上要花多长时间?

5、（在NEC Earth Simulator上花292秒）n694. 02指数级时间都那么糟糕吗?Earth simulator计算机需要计算机需要292秒计算秒计算F200.Time in seconds Interpretation 210 17 分分 220 12 日日 230 32 年年 240 山洞绘画作品山洞绘画作品 (一万五千年到一万七千年之间一万五千年到一万七千年之间) 245 直立人直立人发现火发现火 251 恐龙灭绝恐龙灭绝 257 地球形成地球形成 260 宇宙起源宇宙起源 剖剖 析析为什么花这么长时间为什么花这么长时间?让我们剖析该递归function Fib1(n)if

6、 n = 1 return 1if n = 2 return 1return Fib1(n-1) + Fib1(n-2)同一个子问题被反复求解同一个子问题被反复求解! 学习学习算法算法要点要点: 理解算法的概念。理解算法的概念。理解什么是程序，程序与算法的区别和理解什么是程序，程序与算法的区别和内在联系。内在联系。掌握算法的计算复杂性概念。掌握算法的计算复杂性概念。掌握用掌握用C+/JAVA语言描述算法的方法。语言描述算法的方法。1.1算法的基本概念算法的基本概念 算法（算法（Algorithm）：即在）：即在有限步骤有限步骤内解一个数学问内解一个数学问题的过程，步骤中常常包括某一操作的重复。

7、（韦氏题的过程，步骤中常常包括某一操作的重复。（韦氏词典）词典） 一个算法是解决一个问题或实现某一目标的逐步过程。一个算法是解决一个问题或实现某一目标的逐步过程。（广义）（广义） 算法是有穷规则的集合，规定了一个解决某一特定类算法是有穷规则的集合，规定了一个解决某一特定类型问题的运算序列。（型问题的运算序列。（D.E.Knuth 唐纳德.E.克努特) 输入性输入性：有零个或多个外部量作为算法的输入。：有零个或多个外部量作为算法的输入。 输出性输出性：算法产生至少一个量作为输出。：算法产生至少一个量作为输出。 确定性确定性：算法中每条指令清晰，无歧义。：算法中每条指令清晰，无歧义。 有穷性有穷性

8、：算法中每条指令的执行次数有限，执行每条指令：算法中每条指令的执行次数有限，执行每条指令的时间也有限。（计算过程，时效）的时间也有限。（计算过程，时效） 可行性：可行性： 算法原则上能够精确地运行，而且人们用笔和算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。纸做有限次运算后即可完成。 是算法用某种程序设计语言的具体实现。是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质程序可以不满足算法的性质(4)(4)即有穷性即有穷性。如操作系统如操作系统 算法是满足上述性质的指令序列。算法是满足上述性质的指令序列。程序：1.1.1算法的特征算法的特征 欧几里德算法mnr例：欧

9、几里德算法例：欧几里德算法辗转相除法求两辗转相除法求两个自然数个自然数 m 和和 n 的最大公约数的最大公约数 输入输入m 和和n； 求求m除以除以n的余数的余数r； 若若r等于等于0 0，则，则n为最大公约数，算法结束；为最大公约数，算法结束； 否则执行第步；否则执行第步； 将将n的值放在的值放在m中，将中，将r的值放在的值放在n中；中； 重新执行第步。重新执行第步。欧几里德算法欧几里德算法1.1.1算法的算法的4个标准个标准 正确性正确性：在合理的数据输入下，能：在合理的数据输入下，能在有限的时间内得出正确的结果。在有限的时间内得出正确的结果。 可读性可读性：应易于人的理解，易于调：应易于

10、人的理解，易于调试。试。 健壮性健壮性：具备检查错误和对错误进：具备检查错误和对错误进行适当处理的能力。行适当处理的能力。 效率效率：算法执行时所需计算机资源：算法执行时所需计算机资源的多少，包括运行时间和存储空间。的多少，包括运行时间和存储空间。1.1.3 算法的描述形式算法的描述形式（1 1）自然语言）自然语言优点：容易理解优点：容易理解缺点：冗长、不够严谨、二义性缺点：冗长、不够严谨、二义性使用方法：粗线条描述算法思想使用方法：粗线条描述算法思想 注意事项：避免写成自然段注意事项：避免写成自然段（2 2）算法框图法）算法框图法 优点：流程图、盒图，流程直观、优点：流程图、盒图，流程直观、

11、简洁、明了，便于理解和交流简洁、明了，便于理解和交流 缺点：缺少严密性、灵活性缺点：缺少严密性、灵活性使用方法：描述简单算法使用方法：描述简单算法注意事项：注意抽象层次注意事项：注意抽象层次1.1.3 算法的描述形式算法的描述形式N开始输入m和n r=m % nr=0m=n；n=r 输出n结束Y欧几里德算法欧几里德算法（3 3） 伪代码语言描述法伪代码语言描述法伪代码（伪代码（Pseudocode）：介于自然语言和）：介于自然语言和程序设计语言之间的方法，它采用某一程序程序设计语言之间的方法，它采用某一程序设计语言的基本语法，操作指令可以结合自设计语言的基本语法，操作指令可以结合自然语言来设计

12、。然语言来设计。 （算法语言）算法语言）优点：表达能力强，抽象性强，容易理解优点：表达能力强，抽象性强，容易理解1.1.3 算法的描述形式算法的描述形式 1. r = m % n; 2. 循环直到 r 等于0 2.1 m = n; 2.2 n = r; 2.3 r = m % n; 3. 输出 n ;欧几里德算法欧几里德算法（4 4）高级程序设计语言描述法）高级程序设计语言描述法优点：能由计算机执行优点：能由计算机执行 缺点：抽象性差，对语言要求高缺点：抽象性差，对语言要求高使用方法：算法需要验证使用方法：算法需要验证注意事项：将算法写成子函数注意事项：将算法写成子函数1.1.3 算法的描述形

13、式算法的描述形式#include int CommonFactor(int m, int n) int r=m % n; while (r!=0) m=n; n=r; r=m % n; return n;void main( ) coutCommonFactor(63, 54)endl;欧几里德算法1.2 算法设计的一般过程算法设计的一般过程充分理解要解决的问题充分理解要解决的问题数学模型拟制数学模型拟制-建立符合要求数学模型，设计相关约束条件建立符合要求数学模型，设计相关约束条件算法详细设计算法详细设计-选择算法设计策略，确定数据结构选择算法设计策略，确定数据结构算法描述算法描述-描述工具将

14、算法具体过程描述下来描述工具将算法具体过程描述下来算法思路的正确性验证算法思路的正确性验证 算法分析算法分析-时间、空间复杂性时间、空间复杂性算法的计算机实现和测试算法的计算机实现和测试 文档资料的编制文档资料的编制 算法设计的一般过程算法设计的一般过程 1 1理解问题理解问题2 2预测所有可能的输入预测所有可能的输入3. 3. 在精确解和近似解间做选择在精确解和近似解间做选择 4. 4. 确定适当的数据结构确定适当的数据结构 5 5算法设计技术算法设计技术6 6描述算法描述算法 7 7跟踪算法跟踪算法 8 8分析算法的效率分析算法的效率 9 9根据算法编写代码根据算法编写代码 著名公式著名公

15、式 Algorithm + Data Structure = Programming好的算法好的算法 提高求解问题的效率提高求解问题的效率 节省存储空间节省存储空间 需要解决的问题需要解决的问题 问题问题一个求解一个求解算法：算法设计技术算法：算法设计技术 算法算法算法的评价：算法的评价： 算法分析技术算法分析技术1.3 算法分析算法复杂性算法复杂性 = 算法运行时所需要的计算机资源的量算法运行时所需要的计算机资源的量 时间复杂性、空间复杂性时间复杂性、空间复杂性影响时间复杂性的因素影响时间复杂性的因素 问题规模问题规模n、输入序列、输入序列I、算法本身、算法本身A影响空间复杂性的因素影响空间

16、复杂性的因素 算法本身、输入输出数据、辅助变量算法本身、输入输出数据、辅助变量算法复杂性的权衡算法复杂性的权衡 时间复杂度和空间复杂度相互影响时间复杂度和空间复杂度相互影响（时间换空间或空间换时间）（时间换空间或空间换时间）1.3 算法分析 三种情况下的复杂性（结合顺序查找操作）三种情况下的复杂性（结合顺序查找操作） 最好情况最好情况Tmin（N)1次次 最坏情况最坏情况Tmax（N)N次次 平均情况平均情况Tavg（N)(N+1)/2算法复杂性分析 当问题规模增大时，复杂当问题规模增大时，复杂度的极限行为度的极限行为称为称为算法的算法的渐进时间复杂度渐进时间复杂度。算法算法时间复杂度时间复杂

17、度最大问题规模最大问题规模1秒秒1分分1小时小时A1n10006*1043.6*106A2nlogn14048932.0*105A3N2312441897A4N31039153A52n91521算法算法时间复杂度时间复杂度加速前最大问题规加速前最大问题规模模加速后最大问题规加速后最大问题规模模A1nS110*S1A2nlognS2约为约为10*S2A3N2S33.16*S3A4N3S42.15*S4A52nS5S5+3.3假设下一代计算机的速度是目前的10倍，下表是计算机加速后在相同的时间内可以解决的问题规模增量。 算法渐近复杂性态算法渐近复杂性态 设算法的运行时间为设算法的运行时间为T(n)

18、，如果存在，如果存在T*(n)，使得使得 就称就称T*(n)为算法的渐进复杂性态或渐进时为算法的渐进复杂性态或渐进时间复杂性。间复杂性。0)()()(lim*nTnTnTn举例： 假设算法A的运行时间表达式为T1(n) T1(n)=30n4+20n3+40n2+46n+100 假设算法B的运行时间表达式为T2(n) T2(n)=1000n3+50n2+78n+10随着n的增大，对算法的执行时间影响最大的是最高次方。算法A的运行时间可记为：T*1(n)n4算法B的运行时间可记为：T*2(n)n3 渐近符号渐近符号: O-上界上界 -下界下界 -精确界（上界和下界）精确界（上界和下界）渐进符号渐进

19、符号 1. 大大O符号符号(上界）上界）定义定义1.1 若存在两个正的常数若存在两个正的常数c和和n0，对于任意，对于任意nn0，都有，都有T( (n)cf( (n) )，则称，则称T( (n) )=O( (f( (n)n0问题规模问题规模n执执行行次次数数n0之前的之前的情况无关情况无关紧要紧要T( (n) )cf( (n) )f(N)是是T(N)的一个的一个上界上界，即即T(N)的阶不高于的阶不高于f(N)的阶的阶 根据根据O O的定义，的定义，容易证明它有如下运算规则：容易证明它有如下运算规则： (1)O(f)+O(g)=O(max(f,g) (1)O(f)+O(g)=O(max(f,g

20、)； (2)O(f)+O(g)=O(f+g) (2)O(f)+O(g)=O(f+g)； (3)O(f)O(g)=O(fg) (3)O(f)O(g)=O(fg)； (4)O(Cf(N)=O(f(N) (4)O(Cf(N)=O(f(N)，其中，其中C C是一个正的常数；是一个正的常数； (5)f=O(f)(5)f=O(f)2. 大大符号符号 （下界）定义定义1.2 若存在两个正的常数若存在两个正的常数c和和n0，对于任意，对于任意nn0，都有，都有T( (n)cg( (n) )，则称，则称T( (n) )=( (g( (n)n0问题规模问题规模n执执行行次次数数n0之 前 的之 前 的情 况 无

21、关情 况 无 关紧要紧要T( (n) )cg( (n) )渐进符号（续）渐进符号（续） g(N)是是T(N)的一个的一个下界下界，即即T(N)的阶不低于的阶不低于g(N)的阶的阶3. 符号符号（同阶）（同阶）定义定义1.3 若存在三个正的常数若存在三个正的常数c1、c2和和n0，对于任意，对于任意nn0都有都有c1f( (n)T( (n)c2f( (n) )，则称，则称T( (n) )=(f( (n) n0问题规模问题规模n执执行行次次数数n0之 前 的之 前 的情 况 无 关情 况 无 关紧要紧要T( (n) )c2f( (n) )c1f( (n) )渐进符号（续）渐进符号（续） 当且仅当当

22、且仅当f(N)=O(g(N)f(N)=O(g(N)且且f(N)= f(N)= (g(N)(g(N)。称称f(N)f(N)与与g(N)g(N)同阶同阶。 例: 求T(n)=10n+4的渐进上界 O(n)算法分析中常见的复杂性函数算法分析中常见的复杂性函数 几种常见的时间复杂度函数按数量级从小几种常见的时间复杂度函数按数量级从小到大的顺序依次是：到大的顺序依次是： (1), (logn)，(sqrt(n)，(n)，(nlogn)，(n2)，(n3)，(2n)，(n!) 在多项式中，在多项式中，n的最高次指数的最高次指数是最主要的决是最主要的决定因素，常数项、低次幂项和系数都是次定因素，常数项、低次

23、幂项和系数都是次要的。要的。例：求T(n)=amnm+am-1nm-1+a1n+a0的上界、下界根据定理1T(n)=(nm)时间复杂度分析的基本规则时间复杂度分析的基本规则 主要考虑可执行语句的情况：主要考虑可执行语句的情况： 输入、输出、赋值语句，为输入、输出、赋值语句，为O（1）；）； 顺序结构顺序结构，采用渐进式，采用渐进式O的求和规则来进行计算；的求和规则来进行计算； 选择结构选择结构，考虑判定后所执行语句的执行时间，考虑判定后所执行语句的执行时间O（max(T(s1), T(s2)）；）； 循环结构循环结构，考虑循环判定条件和循环体语句的执行时，考虑循环判定条件和循环体语句的执行时间

24、，采用渐进式间，采用渐进式O的乘积规则来进行计算；的乘积规则来进行计算； 复杂算法，先分割，然后采用渐进式复杂算法，先分割，然后采用渐进式O的求和规则和乘的求和规则和乘法规则来计算整个算法的时间复杂度；法规则来计算整个算法的时间复杂度； 基本语句基本语句对算法运行时间贡献最大的原操作语句。对算法运行时间贡献最大的原操作语句。 当算法时间复杂性只依赖于问题规模时，选择基本语句执当算法时间复杂性只依赖于问题规模时，选择基本语句执行次数来作为运行时间行次数来作为运行时间T(n)建立的依据。建立的依据。 例：求数组中元素最大值例：求数组中元素最大值空间复杂度空间复杂度 算法所占用的存储空间包括算法所占

25、用的存储空间包括 算法自身 输入、输出输入、输出 辅助空间辅助空间 空间复杂度空间复杂度S(n)=O(f(n)，以最坏情况来分，以最坏情况来分析析 例：例：插入法升序排序插入法升序排序void insert_sort(int n,int s) int a,i,j; for (i=1;i=0; & sja) sj+1=sj; j-; sj+1=a; 1.4 递归（是算法设计与描述的有力工具是算法设计与描述的有力工具） 子程序（或函数）直接调用自己或通过一系列调用语句间接调用自已，称为递归。直接或间接调用自身的算法称为递归算法 。 采用递归算法来求解问题的一般步骤： 分析问题，寻找递归关系 找出停

26、止条件 构建函数体n的阶乘00)!1(1!nnnnn停止条件停止条件递归关系递归关系停止条件与递归关系是递归函数的两个要素，停止条件与递归关系是递归函数的两个要素，递归函数只有具备了这两个要素，才能在有限递归函数只有具备了这两个要素，才能在有限次计算后得出结果。次计算后得出结果。Long long fun(int n) if(n0) printf(“ illegal number!n ”); break; else if(n=0) return 1; else return n*fun(n-1);例：例：排列问题排列问题 问题描述问题描述 n个元素，它们的编号为个元素，它们的编号为1,2,n，

27、排列问题的，排列问题的目的是生成这目的是生成这n个元素的全排列。个元素的全排列。 解题步骤解题步骤 分析递归关系分析递归关系 找出停止条件找出停止条件 设计递归函数设计递归函数 算法设计思路算法设计思路 将规模为将规模为n的排列问题转化为规模为的排列问题转化为规模为n-1的排列的排列问题。问题。 将规模为将规模为n-1的排列问题转化为规模为的排列问题转化为规模为n-2的排的排列问题列问题 将问题规模一级一级降至将问题规模一级一级降至1，1个元素的排列是个元素的排列是它本身，此时到达递推的停止条件。数组中的它本身，此时到达递推的停止条件。数组中的元素即为元素即为1个排列，然后进行回归依次得到其个

28、排列，然后进行回归依次得到其它的排列。它的排列。共要递归共要递归K次（次（K=n，n-1,n-2，1)当当k=1 输出一个排列输出一个排列 如何如何将规模为将规模为n的排列问题转化为规模为的排列问题转化为规模为n-1的排的排列问题。列问题。步骤步骤1：数组的首元素为第一个元素，还需生成后面：数组的首元素为第一个元素，还需生成后面n-1个元素全排列。个元素全排列。步骤步骤2：将数组的第一个元素和第二个元素交换，数组的：将数组的第一个元素和第二个元素交换，数组的首元素为第二个元素，还需生成后面首元素为第二个元素，还需生成后面n-1个元素全排列。个元素全排列。步骤步骤3：将数组的第一个元素和第三个元

29、素交换，数组的：将数组的第一个元素和第三个元素交换，数组的首元素为第三个元素，还需生成后面首元素为第三个元素，还需生成后面n-1个元素全排列。个元素全排列。步骤步骤4：步骤步骤n: 数据结构： int An-按次序存放1n个数排列算法 void perm(int a,int k,int n) if (k=1) 输出一个排列 else for(i=n-k ;in;i+) swap( an-k,ai); perm( a,k-1, n); swap( an-k,ai); 时间复杂度： 采用后向代入法计算可得到通项公式： T(n) =nT(n-1) =n(n-1)T(n-2) = =n(n-1)(n-

30、2) .2T(1)=n! 时间复杂度：O(n!)1n1)nT(n1nO(1)T(n) 递归算法的空间复杂度：递归算法的空间复杂度：算法的递归深度算法的递归深度 全排列算法全排列算法perm共执行了共执行了n次递归次递归 深度为深度为n 空间复杂度空间复杂度(递归递归)：O(n)回到Fibonacci数列问题function Fib1(n)if n = 1 return 1if n = 2 return 1return Fib1(n-1) + Fib1(n-2)同一个子问题被反复求解!Fibonacci数列一个较好的算法数列一个较好的算法子问题子问题: F1, F2, , Fn. 依次求解它们并

31、依次求解它们并保存它们的值保存它们的值!function Fib2(n)Create an array fib1.nfib1 = 1fib2 = 1for i = 3 to n: fibi = fibi-1 + fibi-2return fibn1 它返回正确的答案吗？它返回正确的答案吗？2 它有多快它有多快?运算数与运算数与n成比例成比例. 以前的方法以前的方法: 20.7nF200 现在可在合理时间内计算出来现在可在合理时间内计算出来, F2000 和和 F20000也一样也一样.启示启示 : 恰当的算法使事情彻底改观恰当的算法使事情彻底改观 。第三个算法第三个算法用矩阵重写用矩阵重写 F

32、0 = 0, F1 = 1, Fn = Fn-1 + Fn-2 如下如下:10211110FFFF102213211101110FFFFFF10111110.1110FFFFFFnnnnnnnM1110因此只需快速计算因此只需快速计算多项式级多项式级 vs. 指数级指数级运行时间如运行时间如 n, n2, n3 是是多项式级多项式级。运行时间如运行时间如 2n, en, 2n 是指数级是指数级.多项式是适当的多项式是适当的指数级是不适当的指数级是不适当的在算法分析中，这是最基本的一个分界线在算法分析中，这是最基本的一个分界线.1.5 基本数据结构 顺序表链表 连续存储离散存储 定位、插入、删除

33、 栈队列 FILOFIFO Top、bottomFront、Rear 树树概念概念 基本术语基本术语结点的度:树的度:叶子结点:分支结点:分支的个数树中所有结点的度的最大值度为零的结点度大于零的结点DHIJM孩子孩子结点结点、双亲双亲结点结点、兄弟兄弟结点结点、堂兄弟堂兄弟祖先祖先结点结点、子孙子孙结点结点结点的层次结点的层次: :树的深度：树的深度：ABCDEFGHIJMKL假设根结点的层次为假设根结点的层次为1,1,它的孩子结点它的孩子结点为第二层，依此类推一个结点所在的为第二层，依此类推一个结点所在的层次，为其双亲结点所在的层次加层次，为其双亲结点所在的层次加1 1。树中叶子结点所在的最

34、大层次树中叶子结点所在的最大层次任何一棵非空树是一个二元组任何一棵非空树是一个二元组 Tree = （root，F）其中：其中：root 被称为根结点，被称为根结点， F 被称为子树森林被称为子树森林森林：森林：是是 m（m0）棵互）棵互不相交的树的集合不相交的树的集合ArootBEFKLCGDHIJMF 树的存储结构 双亲存储结构双亲存储结构 A D B C G E F A -1 B 0 C 0 D 0 E 2 F 2 G 2 0 1 2 3 4 5 6 (a) (b) typedef struct ElemType data; int parent;PtreeMaxSize; 链存储结构链存储结构 A B C F D E (a) G A B C D E F G (b) typedef struct node ElemType data; struct node*sonsMaxSons;TSonNode; 图图 定义定义图图(Graph)G(Graph)G由两个集合由两个集合V(Vertex)V(Vertex)和和E