算法设计与分析(复习).pptVIP

算法设计与分析

2010.9

(ACM创新实验班);一、算法根底;时效性：实际问题往往都有时间要求。

例：国际象棋〔启发〕

数值天气预报

只有在要求的时间内解决问题才是有意义的。;2.算法分析根底

1)分析算法的目的:在解决同一问题的不同算法之间比较性能的好坏，从而运行好的算法，改进差的算法，防止无益的人力和物力浪费。对算法的性质作深入了解，从而可以进一步优化算法，让其更好地工作。

2)重要的假设和约定

计算机模型的假设

计算的约定：时间囿界于常数的运算和时间非囿界于常数的运算

工作数据集的选择：了解算法最好、最坏和平均等执行情况;3.事前分析：统计算法中各类运算的执行次数—频率计数，表示称为关于问题规模的形式简单的特征函数。

函数表达式的数量级〔阶〕：函数表达式中的最高次项的次数，是衡量频率计数的“大小”的一种测度。

限界函数：用频率计数函数表达式中的最高次项表示限界函数，记为：g(n)，通常是关于n的形式简单的函数式，如：logn。

(事后测试);4.计算时间的渐近表示

算法时间/空间复杂度的限界函数常用的有三个：上界函数、下界函数、“均值”函数。定义如下：

记：算法的实际计算时间为f(n)，计算时间的限界函数为g(n)，其中，

n是问题规模的某种测度。

f(n)是与机器及语言有关的量。

g(n)是事前分析的结果，一个形式简单的函数，与频率计数有关、而与机器及语言无关。

;定义1.1〔上界函数〕如果存在两个正常数c和n0，对于所有的n≥n0，有|f(n)|≤c|g(n)|，那么记作f(n)=Ο(g(n))。

定义1.2〔下界函数〕如果存在两个正常数c和n0，对于所有的n≥n0，有|f(n)|≥c|g(n)|，那么记作f(n)=Ω(g(n))。

定义1.3〔“平均情况”〕如果存在正常数c1，c2和n0，对于所有的n≥n0，有c1|g(n)|≤|f(n)|≤c2|g(n)|，那么记作

;[定理1.1大O比率定理]对于函数f(n)和g(n)，假设存在，那么f(n)=O(g(n))，当且仅当存在确定的常数c，有≤c。;算法时间复杂度的分类;限界函数的性质;用于估算复杂性阶的定理;定理：设d(n)、e(n)、f(n)和g(n)是将非负整数映射到非负实数的函数，那么

(1)如果d(n)是O(f(n))，那么对于任何常数a0,ad(n)是O(f(n))；

(2)如果d(n)是O(f(n))，e(n)是O(g(n))，那么d(n)+e(n)是O(f(n)+g(n))；

(3)如果d(n)是O(f(n))，e(n)是O(g(n))，那么d(n)e(n)是O(f(n)g(n))；

(4)对于任意固定的x0和a1，nx是O(an)；

(5)对于任意固定的x0，lognx是O(logn)；

(6)对于任意固定的常数x0和y0，logxn是O(ny)；

;4〕o,ω记号;O和o的区别;定义1.5ω记号

形式1：对任意正常数c，存在常数n0＞0，使对所有的n≥n0，有c|g(n)|≤|f(n)|，那么记作：

f(n)=ω(g(n))。

形式2：假设那么记f(n)=o(g(n))。

例：n2/2=ω(n)，但n2/2≠ω(n2);Ω和ω的区别;5.有三种常用的方法：

数学归纳法

反证法

反例法

;二、递归与递归式;递归是一种强有力的设计方法

与数学模型一致

表述简单、清晰、代码量少

可读性强、容易证明正确性

递归的问题：执行时间长、运行效率低，特别是占用空间多，容易造成系统栈的溢出。

主要原因：递归调用时有大量的现场保护与恢复操作，在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储，递归层次数过多容易造成栈溢出等。;3.怎么克服递归的效率问题？

——化递归为递推

递归：递归是一种从上至下的“分解求解“的过程，即不断地把大问题分解为小问题，直到小问题规模足够小，然后求解并进行递归返回和结果合并。——效率差！

递推：递推是一种从下往上的“合并求解“过程，即从解决小问题出发，记录小问题的答案，并根据已有的小问题的答案，把问题往大里扩展，“滚雪球”，直到到达大问题的规模为止。并通常用迭代〔循环〕的方式实现，而不是递归调用，一般认为效率上比递归好。;2.递归式及其求解;2)递归式的求解

求解递归式就是化简递归式，以得到形式简单的限界函数表示〔即O、Ω、Θ的表示〕。