算法分析（一）：数学基础

定义

1. 如果存在正常数 c 和 n₀使得当 N≥n₀时 T(N)≤cf(N),则计为 T(N)=O(f(N))。
2. 如果存在正常数 c 和 n₀使得当 N≥n₀时 T(N)≥cg(N),则计为 T(N)=Ω(g(N))。
3. T(N)=θ(h(N))当且仅当 T(N)=O(h(N))和 T(N)=Ω(g(N))。
4. 任意正常数 c 都存在常数 n₀使得当 N≥n₀时 T(N)<cp(N),则 T(N)=o(p(N))。

看不懂没关系，算法主要用这些来比较相对增长率，定义中四个公式分别表示

1. T(N)的增长率小于或等于 f(N)的增长率，f(N)是 T(N)的上界（upper bound）
2. T(N)的增长率大于或等于 g(N)的增长率，T(N)是 f(N)的下界（lower bound）
3. T(N)的增长率等于 h(N)的增长率
4. T(N)的增长率小于 p(N)的增长率

eg:

N³比 N²增长快，则可以表示为 N²=O(N³)

需要掌握的结论

1. 如果 T₁(N)=O(f(N))且 T₂(N)=O(g(N)),那么 (a) T₁(N)+T₂(N)=O(f(N)+g(N));直观表达为 max(O(f(N)),O(g(N)))。
   (b) T₁(N)*T₂(N)=O(f(N)*g(N))。
2. 如果 T(N)是一个 k 次多项式，则 T(N)=θ(N^k)
3. 对任意常数 k，log^kN=O(N);对数增长的特别缓慢。

注意

1. 尽量不要将常数或者低阶项放入大 O 中，因为算法分析中常数和低阶项很有可能被忽略。
2. 总能通过计算极限 lim_N→∞f(N)/g(N)来确定两个函数的相对增长率，必要可使用洛必达法则。有四种可能值
   2.1 极限为 0：f(N)=o(g(N))。
   2.2 极限是 c≠0：f(N)=θ(g(N))。
   2.3 极限是 ∞：g(N)=o(o(f(N)))。
   2.4 极限摆动：二者无关。

参考资料《数据结构与算法分析》