数据结构：思想与方法-翁惠玉-27783第一章幻灯片.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 渐进表示法 算法的运行时间函数可能是一个很复杂的函数，如何比较这些函数并从中选取出一个好的算法呢？ 时间性能主要考虑的是问题规模很大的时候运行时间随问题规模的变化规律 渐进表示法：不考虑具体的运行时间函数，只考虑运行时间函数的数量级 * 渐进表示法 定义：(大O) 如果存在正的常数c和N0，满足当N=N0时有T(N)= cF(N)，则T(N)是O(F(N))。 定义：(大Ω) 如果存在正的常数c和N0，满足当N=N0时有T(N) ≥ cF(N)，则T(N)是?(F(N))。 定义：(大?) 当且仅当T(N)是O(F(N))，并且T(N)又是?(F(N))，则T(N)是?(F(N))。 定义：(小O) 当且仅当T(N)是O(F(N))，并且T(N)不是? (F(N))，则T(N)是o(F(N))。 * 大O表示法实例 设 T(n) = (n+1)2 那么，取n0 = 1 及 c=4 时， T(n) = cn2 成立。 所以，T(n) = O(n2) 大O表示法就是取运行时间函数的主项 * F(N)的选择 大O表示法的O是单词Order的首字母，表示“数量级” 大O表示法并不需要给出运行时间的精确值，而只需要给出一个数量级，表示当问题规模很大时算法运行时间的增长是受限于哪一个数量级的函数 在选择F(N)时，通常选择的是比较简单的函数形式，并忽略低次项和系数。 * 典型的增长率 c 常量 logN 对数 Log2N 对数的平方 N 线性 NlogN NlogN N2 平方 N3 立方 2N 指数 * 算法按时间复杂度分类 多项式时间：渐进时间复杂度有多项式时间限界的算法 指数时间算法：渐进时间复杂度有指数时间限界的算法 多项式时间复杂度的关系： O(1) O(logN) O(N) O(NlogN) O(N2) O(N3) 指数时间复杂度的关系： O(2N) O(N!) O(NN) * 算法分析 空间复杂度的概念 时间复杂度的概念 算法运算量的计算 渐进表示法 时间复杂度的计算 算法的优化 * 大O表示法的计算 时间复杂度的计算先定义标准操作，再计算标准操作的次数，得到一个标准操作次数和问题规模的函数。然后取出函数的主项，就是它的时间复杂度的大O表示。 简化方法：根据两个定理。 * 大O表示法的定理 求和定理：假定T1(n)、T2(n)是程序P1、P2的运行时间，并且T1(n)是O(f(n))的，而T2(n)是O(g(n))的。那么，先运行P1、再运行P2 的总的运行时间是：T1(n)＋T2(n)＝O(MAX(f(n)，g(n))。 求积定理：如果T1(n) 和 T2(n)分别是O(f(n))和O(g(n))的，那么T1(n)×T2(n)是O(f(n)×g(n)) 的。 * 大O表示法的计算规则 规则1：每个简单语句，如赋值语句、输入输出语句，它们的运行时间与问题规模无关，在每个计算机系统中运行时间都是一个常量，因此时间复杂度为 O(1)。 规则2：条件语句，if 条件 then 语句 else 语句，的运行时间为执行条件判断的代价 ，一般为O(1)，再加上执行 then 后面的语句的代价(若条件为真)，或执行else 后面的语句代价(若条件为假)之和，即max(O(then子句)，O(else子句))。 * 规则3：循环语句的执行时间是循环控制行和循环体执行时间的总和。循环控制一般是一个简单的条件判断，因此循环语句的执行时间是循环体的运行时间乘循环次数。 规则4：嵌套循环语句，对外层循环的每个循环周期，内存循环都要执行它的所有循环周期，因此，可用求积定理计算整个循环的时间复杂度，即最内层循环体的运行时间乘所有循环的循环次数。例语句： for (i=0; in; i++) for (j=0; jn; j++) k++; 的时间复杂性为O(n2) * 连续语句：利用求和定理把这些语句的时间复杂性相加。例程序段： for (i=0; in; i++) a[i]=0; for (i=0; in; i++) for (j=0; jn; j++) a[i]= i+j; 有两个连续的循环组成。第一个循环的时间复杂度为O（n），第二个循环的时间复杂度为O（n2）。根据求和定理，整段程序的的时间复杂性为O(n2) * 大O的简化计算 在程序中找出最复杂、运