算法设计与分析designandanalysisofcomputeralgorithm.ppt

定义： 基本运算：算法中最关键的运算（耗时最多的）。 薄记运算（booking）：算法中除基本运算以外的运算。 输入规模：指问题输入的数据量，问题的大小。 例： 问题 关键运算 输入规模 L中查找X 比较 表元个数 矩阵相乘 加，乘 阶数 表排序 比较，交换 表元个数 遍历树 访问结点 结点个数 算法的存储空间需求 空间复杂度：算法所需存储空间的度量，记作： S(n)=O(f(n)) 其中n为问题的规模(或大小)。 计算机运行程序所需的空间包括：指令空间、数据空间和环境栈空间。 指令空间用来存储经过编译之后的程序指令。程序所需的指令空间的大小取决于如下因素： 把程序编译成机器代码的编译器；编译时实际采用的编译器选项；目标计算机。 一般情况下，指令空间对于所解决的特定问题不够敏感。 数据空间用来存储所有常量和变量的值。分成两部分：存储常量和简单变量、存储复合变量。 计算方法：结构变量所占空间等于各个成员所占空间的累加；数组变量所占空间等于数组大小乘以单个数组元素所占的空间。例如： double a[100]; 所需空间为100×8＝800 环境栈空间保存函数调用返回时恢复运行所需要的信息。 空间复杂度度量 存储空间的固定部分程序指令代码的空间，常数、简单变量、定长成分(如数组元素、结构成分、对象的数据成员等)变量所占空间 可变部分与实例特性有关的成分变量所占空间、递归栈所用空间、通过new和delete命令动态使用空间 例2 频率计数例子 考虑语句x?x+y在下面三个程序段中的频率计数 x?x+y FC:1 for i?1 to n do x?x+y repeat FC:n for I?1 to n do for j?1 to n do x?x+y repeat Repeat FC:n2 计算时间的渐进表示 定义1.1 如果存在两个正常数c和n0，对于所有的n≥n0，有 |f(n)|≤c|g(n)| 则记作：f(n)=O(g(n)) 因此，当说一个算法具有O(g(n))的计算时间时，指的就是如果此算法用n值不变的同一类数据在某台机器上运行时，所用的时间总是小于|g(n)|的一个常数倍。 g(n)是计算时间f(n)的一个上界函数，f(n)的数量级就是g(n) 时间的渐进表示 定理1.1 若A(n)=amnm+…+a1n+a0是一个m次多项式，则A(n)=O(nm)。 定理表明，变量n的固定阶数为m的任一多项式，与此多项式的最高阶nm同阶。因此，一个计算时间为m阶多项式的算法，其时间都可以用O(nm)来表示。 例如，一个算法的数量级为c1nm1,c2nm2,…cknmk的k个语句，则算法的数量及计算时间就是c1nm1+c2nm2+…+cknmk=O(nm) 其中m=max{mi|1≤ i≤ k} 三点注意: 1． 用来作比较的函数 g(n)应该尽量接近 f(n). 例如 3n+2=O(n2) 松散的界限；3n+2=O(n) 较好的界限 2． 不要产生错误界限。 例如 n2+100n+6，当 n3 时，n2+100n+6106n，由此 就认为 n2+100n+6＝O(n). 3． f(n)=O(g(n))不能写成 g(n)=O(f(n)) 因为两者并不等价。实际上，这里的等号并不是通常 相等的含义。 1. O(f )+O(g)=O( max( f, g ) ) 2. O(f )+O(g)=O(f+g) 3. O(f )·O(g)=O(f·g) 4. 如果 g(n)=O(f (n)),则 O(f )+O(g)=O(f ) 5. f=O( f ) 6. O( c f (n) )=O( f (n) ) 运算规则 算法的分类 从计算时间上可把算法分为两类 多项式时间算法(polynomial time algorithm):可用多项式来对其计算时间限界的算法 O(1)O(logn)O(n)O(nlogn)O(n2)O(n3) 指数时间算法(exponential time algorithm):计算时间用指数函数限界的算法 O(2n)O(n!)O(nn) 时间的渐进表示 定义1.2 如果存