算法和复杂度ppt课件

1、1.3-1.4 算法和算法分析算法: 是对特定问题求解步骤的一种描画，它是指令的有限序列，其中每一条指令表示一个或多个操作。一个算法通常具有五个重要特性: 有穷性 有限步终了 确定性 独一执行途径无歧义 可行性 可以经过根本运算实现实际上可以由人用纸和笔完成 输入 零个或多个输入 输出 一个或多个输出Al Khwarizmi阿勒.霍瓦里松初次提出算法概念，非常强调求解问题有条理的步骤。这是算法亘古不变的中心。1.3.1 算 法 的 概 念算法和数据构造是两个不可分割的一致体程序 = 数据构造 + 算法数据构造经过算法实现操作算法根据数据构造设计程序留意：不要把算法和计算机程序等同起来，后者只是

2、描画前者的手段之一，我们还可以用流程图、方式言语与自动机甚至自然言语描画一个算法。算法设计的要求: 正确性 正确反映需求(经过测试) 可读性 有助于了解、调试和维护 强壮性 完备的异常和出错处置 高效率与低存储的需求 时间、空间的要求1.3.2 算 法 设 计算法设计与分析是计算机科学的中心问题。算法设计与分析是计算机科学的中心问题。常用的算法设计方法有：常用的算法设计方法有：穷举法穷举法将问题空间中的一切求解对象一一列举出来，逐将问题空间中的一切求解对象一一列举出来，逐一分析、处置，并验证结果能否满足给定的条件。一分析、处置，并验证结果能否满足给定的条件。例：例：C+switch语句语句回溯

3、法回溯法将问题的候选解按某种顺序逐一枚举和检验，来将问题的候选解按某种顺序逐一枚举和检验，来寻觅一个满足预定条件的解。当发现当前候选解寻觅一个满足预定条件的解。当发现当前候选解不能够是解时，就退回到上一步重新选择下一个不能够是解时，就退回到上一步重新选择下一个候选解回溯。例：八皇后、迷宫、深度优候选解回溯。例：八皇后、迷宫、深度优先搜索先搜索 分治法和递归法分治法和递归法 遇到一个难以直接处理的大问题时，将遇到一个难以直接处理的大问题时，将其分割成一些规模较小的子问题，以便其分割成一些规模较小的子问题，以便各个击破，分而治之，然后把各个子问各个击破，分而治之，然后把各个子问题的解合并起来，得出

4、整个问题的解。题的解合并起来，得出整个问题的解。例：快速排序、归并排序、二分检索例：快速排序、归并排序、二分检索等等 贪婪法和动态规划法贪婪法和动态规划法 贪婪法的根本思想是从问题的初始形状贪婪法的根本思想是从问题的初始形状出发，根据某种贪婪规范，经过假设干出发，根据某种贪婪规范，经过假设干次的贪婪选择而得出部分最优解，寄希次的贪婪选择而得出部分最优解，寄希望于部分的最优解构建最终的全局最优望于部分的最优解构建最终的全局最优解。解。Prim和和Kruskal算法、算法、Dijkstra算算法法 动态规划是一种将问题实例分解为更小动态规划是一种将问题实例分解为更小的、类似的子问题，并存储子问题的

5、解的、类似的子问题，并存储子问题的解而防止计算反复的子问题，以处理最优而防止计算反复的子问题，以处理最优化问题的算法战略。动态规划法和分治化问题的算法战略。动态规划法和分治法类似？区别？例：法类似？区别？例：Floyd算法、矩阵算法、矩阵连乘积连乘积1.4 算法 分 析算法效率的衡量方法算法效率的衡量方法1事后统计事后统计利用计算机内记时功能。利用计算机内记时功能。缺陷：缺陷：必需先运转根据算法编制的程序；必需先运转根据算法编制的程序；所得时间统计量依赖于硬件、软件等环境要素，掩所得时间统计量依赖于硬件、软件等环境要素，掩盖算法本身的优劣盖算法本身的优劣1.4 算法 分 析 算法效率的衡量方法

6、算法效率的衡量方法2 事前分析估计事前分析估计 一个高级言语程序在计算机上运转所耗费的时间取决一个高级言语程序在计算机上运转所耗费的时间取决于：于：根据的算法选用何种战略根据的算法选用何种战略问题的规模问题的规模程序文语程序文语编译程序产活力器代码质量编译程序产活力器代码质量机器执行指令速度机器执行指令速度 时间复杂度和空间复杂度时间复杂度和空间复杂度算法的时间度量 从算法中选取一种对于研讨的问题来说是根本操作的原操作，以该根本操作反复执行的次数作为算法执行的时间度量。例，for ( j = 1 ；j=n ；j+ )X = X + 1 ；for ( i = 1 ；i=n ；i+ )(c)for

7、 ( i = 1 ；i 时的时间复杂性，被称之为渐进时间复杂度。 空间复杂度：算法的所需的空间和问题规模的函数。记为 S(n)。当 n- 时的时间复杂性，被称之为渐进空间复杂度。 给定两个正值函数 f 和 g，思索以下定义： 定义1： 假设存在正数c和N，对于一切的nN，有f(n)cg(n), 那么f(n)=O(g(n)。 上述定义阐明，假设对于足够大的n，或大于某自然数N的n，存在正数c，使 f 不大于cg，那么 f 是g的大O符号。大大O O符号符号 例如： f(n)=2n2+3n+1=O(n2) 在这里，g(n)=n2，c和N的可选值如表所示： 表 对于函数f(n)=2n2+3n+1=O

8、(n2)，根据大O定义计算得到的c和N的不同值 N 1 2 3 4 5 c 6 4339131613225162大O符号 算法分析中常见的复杂度 O(1) O(lgn) O(n) O(nlgn) O(n2) O(n3) O(2n) O(n!) O(nn) 常数 对数 多项式 指数复杂度举例Time to FinishInput Size (n)O(nx)O(n)O(1)O( lg n)O(an)复杂度举例算法的重要性：算法的重要性：计算机不是万能的，并非一切的算法，计算机都可以计算出有用的结果。差的算法不一计算机不是万能的，并非一切的算法，计算机都可以计算出有用的结果。差的算法不一 定有实践意

9、义。定有实践意义。 举一个例子加以阐明。假定时间复杂性函数的时间单位为举一个例子加以阐明。假定时间复杂性函数的时间单位为 us。函数函数 n=20 n=50 n=100 n=500 1000n .02s .05s .15s .5s1000nlogn .09s .3s .6s 4.5s 100n2 .04s .25s 1s 25s10n3 .02s 1s 10s 21分分nlogn .4s 1.1小时小时 220天天 5 108世纪世纪2n/3 .0001s 0.1s 2.7小时小时 5 108世纪世纪2n 1s 35年年 3 104世纪世纪3n 58分分 2109世纪世纪易性算法易性算法顽性算

10、法顽性算法在大多数的情况下，我们只对时间复杂度感兴趣，它通常计算程序执行过程中赋值和比较操作的次数。 例1： for (i=sum=0; in; i+) Sum +=a i; 赋值2+2n次，渐近复杂度O(n)。确定渐近复杂度确定渐近复杂度 例2： for ( i = 0; i n; i+ ) for ( j = 1, sum=a 0; j = i; j+ ) sum +=a j; cout“sum for subarray 0 through i “issumendl; )()()() 1(31) 1321 (2312312211nOnOnOnnnnninni符号 符号符号 假设存在正数假设

11、存在正数c1,c2c1,c2及及N N，对于一切的，对于一切的nNnN，有，有c1g(n)f(n) c2g(n), c1g(n)f(n) c2g(n), 那么那么f(n)= (g(n)f(n)= (g(n)。 最好、平均和最坏情况有时，算法中根本操作反复执行的次数随问题的输入不同而不同。例，顺序查找算法Status search ( int a ，int n ，int e )for ( i = 0 ；i =n - 1 ；+i )if ( e = ai ) return TRUE ；比较次数的复杂度是多少？return FALSE ；最好、平均和最坏情况 最好情况：算法需求的最少步骤 最坏情况：

12、算法需求的最多步骤 平均复杂度：将处置每个输入所执行的步骤数与该输入出现的概率相乘，然后将一切相乘的结果相加。()()avgiiiCp input steps input()()avgiiiCp input steps input最好、平均和最坏情况有时，算法中根本操作反复执行的次数随问题的输入不同而不同。例，顺序查找算法Status serch ( int a ，int n ，int e )for ( i = 0 ；i =n - 1 ；+i )if ( e = ai ) return TRUE ；最好 1 次比较，最坏 n 次比较，平均 (n+1)/2 次比较。return FALSE ；数据构造的选择 分析问题分析问题 在算法设计之前初步设计数据构造在算法设计之前初步设计数据构