算法设计与分析第1章绪论课件

算法设计与分析第1章绪论第第1章章 绪绪 论论 算法理论的两大论题：算法理论的两大论题：1. 1. 算法设计算法设计2. 2. 算法分析算法分析算法设计与分析第1章绪论1.1 算法的基本概念算法的基本概念1.1.1 为什么要学习算法为什么要学习算法1.1.2 算法及其重要特性算法及其重要特性1.1.3 算法的描述方法算法的描述方法1.1.4 算法设计的一般过程算法设计的一般过程1.1.5 重要的问题类型重要的问题类型算法设计与分析第1章绪论 问题的求解过程：问题的求解过程：分析问题分析问题设计算法设计算法编写程序编写程序整理结果整理结果 程序设计研究的四个层次：程序设计研究的四个层次：算法算法方法学方法学语言语言工具工具1.1.1 为什么要学习算法为什么要学习算法 理由理由1 1：算法：算法程序的灵魂程序的灵魂理由理由2 2：提高分析问题的能力：提高分析问题的能力算法的形式化算法的形式化思维的逻辑性、条理性思维的逻辑性、条理性算法设计与分析第1章绪论1.1.2 算法及其重要特性算法及其重要特性 算法（算法（Algorithm）：对特定问题求解）：对特定问题求解步骤的一种描述，是指令的有限序列。步骤的一种描述，是指令的有限序列。算法设计与分析第1章绪论算法的五大特性：算法的五大特性： 输入：一个算法有零个或多个输入。输入：一个算法有零个或多个输入。 输出：一个算法有一个或多个输出。输出：一个算法有一个或多个输出。 有穷性：一个算法必须总是在执行有穷步之后有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。结束，且每一步都在有穷时间内完成。 确定性：算法中的每一条指令必须有确切的含确定性：算法中的每一条指令必须有确切的含义，对于相同的输入只能得到相同的输出。义，对于相同的输入只能得到相同的输出。 可行性：算法描述的操作可以通过已经实现的可行性：算法描述的操作可以通过已经实现的基本操作执行有限次来实现。基本操作执行有限次来实现。算法设计与分析第1章绪论 欧几里德算法mnr例：欧几里德算法例：欧几里德算法辗转相除法求两辗转相除法求两个自然数个自然数 m 和和 n 的最大公约数的最大公约数算法设计与分析第1章绪论1.1.3 算法的描述方法算法的描述方法 自然语言优点：容易理解缺点：冗长、二义性使用方法：粗线条描述算法思想 注意事项：避免写成自然段算法设计与分析第1章绪论 输入输入m 和和n； 求求m除以除以n的余数的余数r； 若若r等于等于0 0，则，则n为最大公约数，算法结束；为最大公约数，算法结束； 否则执行第否则执行第步；步； 将将n的值放在的值放在m中，将中，将r的值放在的值放在n中；中； 重新执行第重新执行第步。步。欧几里德算法欧几里德算法算法设计与分析第1章绪论 流程图流程图 优点：流程直观优点：流程直观 缺点：缺少严密性、灵活性缺点：缺少严密性、灵活性使用方法：描述简单算法使用方法：描述简单算法注意事项：注意抽象层次注意事项：注意抽象层次算法设计与分析第1章绪论N开始输入m和n r=m % nr=0m=n；n=r 输出n结束Y欧几里德算法欧几里德算法算法设计与分析第1章绪论 程序设计语言程序设计语言优点：能由计算机执行优点：能由计算机执行 缺点：抽象性差，对语言要求高缺点：抽象性差，对语言要求高使用方法：算法需要验证使用方法：算法需要验证注意事项：将算法写成子函数注意事项：将算法写成子函数算法设计与分析第1章绪论#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章绪论 伪代码伪代码算法语言算法语言伪代码（伪代码（Pseudocode）：介于自然语言和）：介于自然语言和程序设计语言之间的方法，它采用某一程序程序设计语言之间的方法，它采用某一程序设计语言的基本语法，操作指令可以结合自设计语言的基本语法，操作指令可以结合自然语言来设计。然语言来设计。优点：表达能力强，抽象性强，容易理解。优点：表达能力强，抽象性强，容易理解。算法设计与分析第1章绪论 1. r = m % n; 2. 循环直到 r 等于0 2.1 m = n; 2.2 n = r; 2.3 r = m % n; 3. 输出 n ;欧几里德算法欧几里德算法算法设计与分析第1章绪论1.1.4 算法设计的一般过程算法设计的一般过程 1 1理解问题理解问题2 2预测所有可能的输入预测所有可能的输入3. 3. 在精确解和近似解间做选择在精确解和近似解间做选择 4. 4. 确定适当的数据结构确定适当的数据结构 5 5算法设计技术算法设计技术6 6描述算法描述算法 7 7跟踪算法跟踪算法 8 8分析算法的效率分析算法的效率 9 9根据算法编写代码根据算法编写代码 算法设计与分析第1章绪论1.1.5 重要的问题类型重要的问题类型 1. 查找问题查找问题2. 排序问题排序问题3. 图问题图问题 4. 组合问题组合问题 5. 几何问题几何问题算法设计与分析第1章绪论1.2 算法分析算法分析1.2.1 渐进符号渐进符号1.2.2 最好、最坏和平均情况最好、最坏和平均情况1.2.3 非递归算法的分析非递归算法的分析1.2.4 递归算法的分析递归算法的分析1.2.5 算法的后验分析算法的后验分析算法设计与分析第1章绪论1.2 算法分析算法分析 算法分析（算法分析（Algorithm Analysis）：对算法所需）：对算法所需要的两种计算机资源要的两种计算机资源时间和空间进行估算时间和空间进行估算 时间复杂性（时间复杂性（Time Complexity） 空间复杂性（空间复杂性（Space Complexity）算法分析的目的：算法分析的目的： 设计算法设计算法设计出复杂性尽可能低的算法设计出复杂性尽可能低的算法 选择算法选择算法在多种算法中选择其中复杂性最低者在多种算法中选择其中复杂性最低者算法设计与分析第1章绪论时间复杂性分析的关键：时间复杂性分析的关键：问题规模：输入量的多少；问题规模：输入量的多少；基本语句：执行次数与整个算法的执行时间基本语句：执行次数与整个算法的执行时间 成正比的语句成正比的语句for (i=1; i=n; i+) for (j=1; j0），则有），则有T( (n) )=O( (nm) )且且T( (n) )=( (n m) )，因此，有因此，有T( (n) )=(n m) )。 算法设计与分析第1章绪论1.2.2 最好、最坏和平均情况最好、最坏和平均情况 例：例： 在一维整型数组在一维整型数组A n 中顺序查找与给定值中顺序查找与给定值k相相等的元素（假设该数组中有且仅有一个元素值为等的元素（假设该数组中有且仅有一个元素值为k） int Find(int A , int n) for (i=0; in; i+) if (Ai= =k) break; return i; 算法设计与分析第1章绪论最好情况：出现概率较大时分析最好情况：出现概率较大时分析最差情况：实时系统最差情况：实时系统平均情况：已知输入数据是如何分布的，平均情况：已知输入数据是如何分布的， 通常假设等概率分布通常假设等概率分布结论：如果问题规模相同，时间代价与输结论：如果问题规模相同，时间代价与输入数据有关，则需要分析最好情况、最坏入数据有关，则需要分析最好情况、最坏情况、平均情况。情况、平均情况。算法设计与分析第1章绪论1.2.3 非递归算法的分析非递归算法的分析 算法算法非递归算法、递归算法非递归算法、递归算法 例：求数组最小值算法例：求数组最小值算法 int ArrayMin(int a , int n) min=a0; for (i=1; in; i+) if (ai + += = =15)2(217)(2nnnTnnT)(10310)212(57257)(22212102nOnnnnnnnnTkkii= = - -= =- -+ += = + += =- - -= = 222112222225)2(52)2(52) 1 (25)2(5)4(5)8(2(2(25)2(5)4(2(25)2(2)(nnnTnnnnTnnnTnnTnTkkk+ + + + += =+ + + += =+ + += =+ += =- - -LL算法设计与分析第1章绪论3. 通用分治递推式通用分治递推式大小为大小为n的原问题分成若干个大小为的原问题分成若干个大小为n/b的子问题，的子问题，其中其中a个子问题需要求解，而个子问题需要求解，而cnk是合并各个子问题是合并各个子问题的解需要的工作量。的解需要的工作量。 + += = =1)(1)(ncnbnaTncnTk = =kkkbkkabanObannObanOnTb)()log()()(log算法设计与分析第1章绪论1.2.5 算法的后验分析算法的后验分析 算法的后验分析（算法的后验分析（Posteriori）也）也称算法的实验分析，它是一种事后计称算法的实验分析，它是一种事后计算的方法，通常需要将算法转换为对算的方法，通常需要将算法转换为对应的程序并上机运行。应的程序并上机运行。算法设计与分析第1章绪论一般步骤：一般步骤：1. 明确实验目的明确实验目的 2. 决定度量算法效率的方法，为实验准备算法的决定度量算法效率的方法，为实验准备算法的程序实现程序实现3. 决定输入样本，生成实验数据决定输入样本，生成实验数据 4. 对输入样本运行算法对应的程序，记录得到的对输入样本运行算法对应的程序，记录得到的实验数据实验数据5. 分析得到的实验数据分析得到的实验数据 算法设计与分析第1章绪论表格法记录实验数据表格法记录实验数据 129,799113,06391,27478,69267,27253,01039,99224,30311,966次数次数900080007000600050004000300020001000规模规模散点图记录实验数据散点图记录实验数据 执行次数或时间 问题规模n算法设计与分析第1章绪论1.3 实验项目实验项目求最大公约数求最大公约数 1. 实验题目实验题目求两个自然数求两个自然数m和和n的最大公约数。的最大公约数。2. 实验目的实验目的 复习数据结构课程的相关知识，实现课程间的平滑过渡；复习数据结构课程的相关知识，实现课程间的平滑过渡； 掌握并应用算法的数学分析和后验分析方法；掌握并应用算法的数学分析和后验分析方法； 理解这样一个观点：不同的算法能够解决相同的问题，这理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。些算法的解题思路不同，复杂程度不同，解题效率也不同。算法设计与分析第1章绪论3. 实验要求实验要求 至少设计出三个版本的求最大公约数算法；至少设计出三个版本的求最大公约数算法； 对所设计的算法采用大对所设计的算法采用大O符号进行时间复杂性分析；符号进行时间复杂性分析；上机实现算法，并用计数法和计时法分别测算算法的上机实现算法，并用计数法和计时法分别测算算法的运行时间；运行时间； 通过分析对比，得出自己的结论。通过分析对比，得出自己的结论。