算法和复杂度

1、1.3-1.4 算法和算法分析,算法和复杂度,2,算法: 是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。,一个算法通常具有五个重要特性:,有穷性 有限步结束,确定性 唯一执行路径（无歧义）,可行性 可以通过基本运算实现（理论上能够由人用纸和笔完成）,输入 零个或多个输入,输出 一个或多个输出,Al Khwarizmi（阿勒.霍瓦里松）首次提出算法概念，十分强调求解问题有条理的步骤。这是算法亘古不变的核心。,1.3.1 算 法 的 概 念,算法和复杂度,3,算法和数据结构是两个不可分割的统一体,程序 = 数据结构 + 算法,数据结构通过算法实现操作,算法根

2、据数据结构设计程序,注意：不要把算法和计算机程序等同起来，后者只是描述前者的手段之一，我们还可以用流程图、形式语言与自动机甚至自然语言描述一个算法。,算法和复杂度,4,算法设计的要求:,正确性 正确反映需求(通过测试),可读性 有助于理解、调试和维护,健壮性 完备的异常和出错处理,高效率与低存储的需求 时间、空间的要求,算法和复杂度,5,1.3.2 算 法 设 计,算法设计与分析是计算机科学的核心问题。 常用的算法设计方法有： 穷举法 将问题空间中的所有求解对象一一列举出来，逐一分析、处理，并验证结果是否满足给定的条件。（例：C+switch语句） 回溯法 将问题的候选解按某种顺序逐一枚举和检

3、验，来寻找一个满足预定条件的解。当发现当前候选解不可能是解时，就退回到上一步重新选择下一个候选解（回溯）。（例：八皇后、迷宫、深度优先搜索）,算法和复杂度,6,分治法和递归法 遇到一个难以直接解决的大问题时，将其分割成一些规模较小的子问题，以便各个击破，分而治之，然后把各个子问题的解合并起来，得出整个问题的解。（例：快速排序、归并排序、二分检索等） 贪心法和动态规划法 贪心法的基本思想是从问题的初始状态出发，依据某种贪心标准，通过若干次的贪心选择而得出局部最优解，寄希望于局部的最优解构建最终的全局最优解。（Prim和Kruskal算法、Dijkstra算法） 动态规划是一种将问题实例分解为更小

4、的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。动态规划法和分治法相似？区别？（例：Floyd算法、矩阵连乘积）,算法和复杂度,7,1.4 算法 分 析,算法效率的衡量方法1 事后统计 利用计算机内记时功能。 缺点： 必须先运行依据算法编制的程序； 所得时间统计量依赖于硬件、软件等环境因素，掩盖算法本身的优劣,算法和复杂度,8,1.4 算法 分 析,算法效率的衡量方法2 事前分析估计 一个高级语言程序在计算机上运行所消耗的时间取决于：依据的算法选用何种策略问题的规模程序语言编译程序产生机器代码质量机器执行指令速度 时间复杂度和空间复杂度,算法和复杂度,9,

5、算法的时间度量,从算法中选取一种对于研究的问题来说是基本操作的原操作，以该基本操作重复执行的次数作为算法执行的时间度量。,基本操作重复执行的次数分别为 1，n，n2,算法和复杂度,10,算法复杂度,问题的规模(n)：或大小。如：矩阵的阶数、图的结点个数、被分类序列的正整数个数 时间复杂度：算法的所需的时间和问题规模的函数。记为 T(n)。当 n- 时的时间复杂性，被称之为渐进时间复杂度。 空间复杂度：算法的所需的空间和问题规模的函数。记为 S(n)。当 n- 时的时间复杂性，被称之为渐进空间复杂度。,算法和复杂度,11,给定两个正值函数 f 和 g，考虑以下定义： 定义1： 如果存在正数c和N

6、，对于所有的nN，有f(n)cg(n), 则f(n)=O(g(n)。 上述定义表明，如果对于足够大的n，或大于某自然数N的n，存在正数c，使 f 不大于cg，则 f 是g的大O符号。,大O符号,算法和复杂度,12,例如： f(n)=2n2+3n+1=O(n2) 在这里，g(n)=n2，c和N的可选值如表所示： 表 对于函数f(n)=2n2+3n+1=O(n2)，根据大O定义计算得到的c和N的不同值,大O符号,算法和复杂度,13,算法分析中常见的复杂度 O(1) O(lgn) O(n) O(nlgn) O(n2) O(n3) O(2n) O(n!) O(nn) 常数 对数 多项式 指数,复杂度举

7、例,算法和复杂度,14,复杂度举例,算法的重要性：,计算机不是万能的，并非所有的算法，计算机都能够计算出有用的结果。差的算法不一 定有实际意义。,举一个例子加以说明。假定时间复杂性函数的时间单位为 us。,函数 n=20 n=50 n=100 n=500 1000n .02s .05s .15s .5s 1000nlogn .09s .3s .6s 4.5s 100n2 .04s .25s 1s 25s 10n3 .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

8、世纪 3n 58分 2109世纪,易性算法,顽性算法,算法和复杂度,16,在大多数的情况下，我们只对时间复杂度感兴趣，它通常计算程序执行过程中赋值和比较操作的次数。 例1： for (i=sum=0; in; i+) Sum +=a i; 赋值2+2n次，渐近复杂度O(n)。,确定渐近复杂度,算法和复杂度,17,确定渐近复杂度,例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 “is”sumendl; ,算法和复杂度,18,符号,符

9、号 如果存在正数c1,c2及N，对于所有的nN，有c1g(n)f(n) c2g(n), 则f(n)= (g(n)。,算法和复杂度,19,最好、平均和最坏情况,有时，算法中基本操作重复执行的次数随问题的输入不同而不同。,例，顺序查找算法,比较次数的复杂度是多少？,return FALSE ；,算法和复杂度,20,最好、平均和最坏情况,最好情况：算法需要的最少步骤 最坏情况：算法需要的最多步骤 平均复杂度：将处理每个输入所执行的步骤数与该输入出现的概率相乘，然后将所有相乘的结果相加。,算法和复杂度,21,最好、平均和最坏情况,有时，算法中基本操作重复执行的次数随问题的输入不同而不同。,例，顺序查找算法,最好 1 次比较，最坏 n 次比较，平均 (n+1)/2 次比较。,return FALSE ；,算法和复杂度,22,数据结构的选择,分析问题 在算法设计