算法分析与设计 课件

算法分析与设计Design and Analysis of Computer Algorithm

教材：计算机算法设计与分析( 教材：计算机算法设计与分析(第3版) 算法设计与分析 王晓东 编著

算法分析与设计 课件

课程简介算法分析与设计是计算机的核心课程之一， 算法分析与设计是计算机的核心课程之一，在众多的计 算机系统软件和应用软件中都要用到本课程的内容。 算机系统软件和应用软件中都要用到本课程的内容。它是操 作系统、编译原理等课程的先行课程， 作系统、编译原理等课程的先行课程，在计算机的理论体系 中占有极其重要的位置。 中占有极其重要的位置。 通过本课程的学习， 通过本课程的学习，使学生掌握算法分析与设计的基本 理论，使学生学会算法分析与设计的基本方法,掌握 掌握计算机科 理论，使学生学会算法分析与设计的基本方法 掌握计算机科 学及应用领域常见的有代表性的非数值算法及算法设计的若 干重要方法，并学会用这些算法解决实际问题。 干重要方法，并学会用这些算法解决实际问题。 本课程以算法设计策略为知识单元， 本课程以算法设计策略为知识单元，介绍算法设计方法 和分析技巧，这些策略包括递归技术、分治、动态规划、贪 和分析技巧，这些策略包括递归技术、分治、动态规划、 心算法、回溯法、分支限界法等策略，它们的内容相对独立。 心算法、回溯法、分支限界法等策略，它们的内容相对独立。 其先修课为高等数学、程序设计、数据结构。 其先修课为高等数学、程序设计、数据结构。

算法分析与设计 课件

本课程主要内容第1章 算法概述 第 2章 第 3章 第 4章 第 5章 第 6章 递归与分治策略 动态规划 贪心算法 回朔法 分支限界法

算法分析与设计 课件

第1章 算法概述学习要点: 学习要点: 理解算法的概念。 理解什么是程序，程序与算法的区别和内在联系。 掌握算法的计算复杂性概念。 掌握算法渐近复杂性的数学表述。

算法分析与设计 课件

软件(software):程序及其各种文档资料的总称 程序(algorithm)=算法+数据结构 算法(procedure):解的描述(程序的灵魂) 数据结构(data structure):现实世界的数据模型 语言(language):实现的工具

算法分析与设计 课件

算法(Algorithm) 算法(Algorithm)算法是指解决问题的一种方法或一个过程。 算法是若干指令的有穷序列，满足性质： (1)输入 输入：有外部提供的量作为算法的输入。 输入 (2)输出 输出：算法产生至少一个量作为输出。 输出 (3)确定性 确定性：组成算法的每条指令是清晰，无歧义的。 确定性 (4)有限性 有限性：算法中每条指令的执行次数是有限的，执 有限性 行每条指令的时间也是有限的。

算法分析与设计 课件

程序(Program) 程序(Program) 程序是算法

用某种程序设计语言的具体实现。 程序可以不满足算法的性质(4)有限性 有限性。 有限性 例如操作系统，是一个在无限循环中执行的程序，因 而不是一个算法。 操作系统的各种任务可看成是单独的问题，每一个问 题由操作系统中的一个子程序通过特定的算法来实现。 该子程序得到输出结果后便终止。

算法分析与设计 课件

算法的描述方法 自然语言– – – – 优点：容易理解 缺点：冗长、二义性 使用方法：粗线条描述算法思想 注意事项：避免写成自然段

欧几里德算法：①输入m和n; ②求m除以n的余数r; ③若r等于0,则n为最大公约数，算法 结束；否则执行第④步； ④将n的值放在m中，将r的值放在n中； ⑤重新执行第②步。

算法分析与设计 课件

流程图– – – – 优点：流程直观 缺点：缺少严密性、灵活性 使用方法：描述简单算法 注意事项：注意抽象层次开始 输入m和n r=m % n r=0 N m=n;n=r 输出n 结束 Y

欧几里德算法：

算法分析与设计 课件

程序设计语言– – – – 优点：能由计算机执行 缺点：抽象性差，对语言要求高 使用方法：算法需要验证 注意事项：将算法写成子函数int CommonFactor(int m, int n) { int r = m % n; while (r!=0) { m = n; n = r; r = m % n; } return n; }

欧几里德算法：#include<iostream.h>

…… 此处隐藏1778字 ……

Meaning: for all data sets big 渐近复杂性分析的记号 enough (i.e., n>n0), the algorithm always executes in less than C|g(n)| 在下面的讨论中，对所有n,f(n) ≥ 0,g(n) ≥ 0。 (1)渐近上界记号O(Big-O) 渐近上界记号O 渐近上界记号 )若存在正常数c和自然数 若存在正常数 和自然数n0 使得当 和自然数 n≥ n 0 时 ， 有 0 ≤ f ( n ) ≤ cg ( n ) ≥ 充分大时有上 则称函数 f(n )在n充分大时有上 在 充分大时有 界, 且g(n)是它的一个上界, 记为 f(n) =O(g (n) ) , 也称 f(n) 的 阶 不 高 于 g ( n ) 的 阶 。c g(n)Running Time

f (n)

n0

Input Size

算法运行时间的上限 算法运行时间的上限 上界的阶越低，则评估就越精确，结果就越有价 上界的阶越低，则评估就越精确， 上界的阶越低 T(n)= 值。例：T(n) =3n2 ,T(n)=O(n2),而n2= 取前者。 O(n3), 取前者。

算法分析与设计 课件

举例：例1 :f(n) = 2n + 3 = O(n) 当n≥3时，2n+3≤3n,所以，可选 = 3,n0 = 3。对于 时 ，所以，可选c , 。对于n≥n0,f(n) , = 2n + 3≤3n,所以，f(n) = O(n),即2n + 3∈O(n)。这意味着， ,所以， , ∈ 。这意味着， 的程序步不会超过3n, 当n≥3时，程序 的程序步不会超过 ，2n + 3 = O(n)。 时 程序2-1的程序步不会超过 。 例2: f(n) = 10n2 + 4n + 2 = O(n2) 对于n≥2时， 有10n2 + 4n + 2≤10n2 + 5n,并且当 对于 时 ， 并且当n≥5时， 时 5n≤n2,因此，可选 = 11, n0 = 5;对于 因此，可选c ;对于n≥n0,f(n) = 10n2 + , 4n + 2≤11n2,所以 所以f(n) = O(n2)。 。 例3: f(n) = n!= O(nn) 对于n≥1,有n(n 1)(n 2) … 1≤nn,因此，可选c = 1,n0 = 对于 ， 因此，可选 ， 1。对于 所以， 。对于n≥n0,f(n) = n!≤nn,所以，f(n) = O(nn)。 , ! 。Hui Gao 21 4/10/2012