函数的渐进复杂性.ppt

* Guess方法Ⅰ： 联想类似的已知T(n) 例1: 求解 , T(1)=1. 解: 展开T(n)若干步,可以猜测 T(n)=O(nlogn). 我们需要证明T(n)=O(nlogn). * 设 1.当n≤m时都成立. 2.则当 n=m+1时 有： 于是有， . （只要C≥1） 用数学归纳法证明猜测的解正确 * *边界条件的问题: 设T(1)=1是边界条件， 则T(1)≤C×1×log1=0不成立。 *边界条件问题的解决： 我们只要求对于n≥n0时，T(n)=O(nlogn). 我们只需看n=2，n=3，或4等，选一个满足 T(n)≤C×nlogn 的最小n0即可。 只需C≥ 2，这与上页的C≥1不矛盾。 * 例2: 求解 解: 只相差一个17. 猜测: 与 当n充分大时 的差别并不大。 因为 相差小，我们可以猜T(n)=O(nlogn). 证明: 可用数学归纳法证明T(n)=O(nlogn). * Guess方法Ⅱ： ---- 猜测loose上、下界，然后减少不确定性范围 例3: 求解 . 解: 首先证明 然后逐阶地降低上界、提高下界。 后面一个包含前面一个（一个比一个高阶）： O(1)∈O(logn)∈O(n)∈O(nlogn)∈O(n2)∈O(n3)∈O(cn)∈O(n!) ?(n)的上一个阶是?(nlogn), O(n2)的下一个阶是O(nlogn)。 * Iteration （循环递归-迭代法 ） 方法: 循环地展开递归方程，把递归方程转化为和式，然后可使用求和技术得解。 §2.4.2 * 例如: * 令 * 方法的关键： ⑴ 达到边界条件时，展开需要的循环次数。 ⑵ 由循环递归过程而得到和式。 注意： ⑴ 在循环中间可能猜出解，此时应停止循环。 ⑵ floor和ceiling使问题复杂化，我们可以假设 方程定义在一个量的幂，如 n=4k 则 可以省略。 * Exercise 1： (作业1 ) 1.算法A1与A2分别有函数复杂性 f1(n)= n2- n + 590 f2(n)= 59n + 50 确定子集n ∈ N ,其中f1小于f2。 2.试证明下面的等式和不等式成立： ①证明 ，其中a≠0 ②证明 * 3.试判定下列函数 f(n) 和 g(n) 的关系： 是 ，还是 , 还是 ? 并说明理由. ⑴. ⑵. ⑶. ⑷. ⑸. ⑹. ⑺. ⑻. * 小于关系什么都不是，=小于等于关系是自反和可迁，=等于关系是等价关系--自反、可迁、对称。 * 衡量两个算法的好坏，应当是在n足够大的情形下，对算法的工作量进行比较。 * 函数增长表： 一般情况下，随着n的增大，增长较慢的算法为最优的算法。 应该选择对数阶或多项式阶的算法，避免使用指数阶的算法。 * 进一步分析可知，要比较两个算法的渐近复杂性的阶不相同时，只要确定出各自的阶，就可以知道哪一个算法的效率高。 换句话说，渐近复杂性分析只要关心 的阶就够了，不必关心包含在 中的常数因子。 所以，我们常常可对 的分析进一步简化，即假设算法中用到的所有不同的运算（基本）各执行一次所需要的时间都是一个单位时间。 * §2.3 复杂性函数的阶 ---- 求解函数的上界“O”，下界“Ω”，同阶“Θ” * 根据以上分析，我们已经给出了简化算法