算法分析 方法简介
算法分析方法讲解
算法分析中常常看到形如T(n) = O( f(n) )的表达式，下面做简单说明：
表达形式：
1.如果存在正 常数c和n 使得 当 N≥n时 T(N)≤ cf(N), z则记为T(N) = O( f(N)). (大O记法。 例如O(N2) 读作大O N平方)
2.如果存在正 常数c和n 使得 当 N≥n时 T(N) < cf(N), z则记为T(N) = o( f(N)).
3.如果存在正 常数c和n 使得 当 N≥n时 T(N) ≥ cg(N), z则记为T(N) = Ω(g(N) ).
4.T(N) = Θ( g(N) ) 当且仅当 T(N) = O( g(N) )和T(N) = Ω(g(N) ).
意义：
上面4中表达式用于说明算法对资源（时间或空间）消耗的相对增长率。
例T(N) = O( f(N) ) 我们说 T(N) 的增长率小于等于f(N)， f(N)为T(N)的上界，同时意味着T(N)为f(N)的下界。
注意：
1.在算法分析时应选择最好的答案。如 g(N)=2N2,那么g(N)=O(N4), g(N)=O(N3), g(N)=O(N2)均成立，但是应选择最好的答案 g(N)=O(N2).
2.算法分析中去掉常数和低阶项,在此过程中精度要求较低
如T(N)=O(2N2) T(N)=O(N2+N) 记为T(N)=O(N2)
3.几种常用函数 增长率表格
函数
名称
C
常数
logN
对数
Log2N
对数平方
N
线型
NlogN
N2
二次
N3
三次
2N
指数
另外在计算 f(n)与g(n)相对增长率时也常常使用 洛必达法则
LimN→∞f(N)/g(N)
极限为0，则 f(N) = o( g(N) )
极限为c != 0,则 f(N) = Θ( g(N) )
极限为∞，则 g(N) = o( f(N) )
极限摆动：不确定
4.平均情形性能常常反映典型的结果，而最坏情形的性能 代表 对任意输入在性能上的一种保证。
一般说来，无特别说明，算法性能以最坏情况的运行时间表示。（原因之一 它对所有输入提供了一个界限，包括特别坏的输入，而平均情况下部提供这样的界）
补充：综合编程 , 其他综合 ,
