算法性能分析

f(n) = O(g(n)) 等价于 0 <= f(n) <= c * g(n)
f(n) = Ω(g(n)) 等价于 f(n) >= c * g(n)
f(n) = Θ(g(n)) 等价于 f(n) 渐进等于 c * g(n)

o 和 ω 分别是 O 和 Ω 的小写字母，因此分别表示严格小于和严格大于

解决递归问题的一些有趣的方法

---

1. 代入法

1. 猜答案（忽略掉常数系数，直接猜函数的最高阶）
2. 利用数学归纳法证明假设

解递归式：
T(n) = 4T(n / 2) + n;

假设：T(n) = O(n³);

1. 猜想： T(n) = O(n³);
2. 归纳：
       T(k) <= c * k³ for k < n;
   3.证明：
       T(n) = 4T(n / 2) + n
               <=4c(n / 2)³ + n;
               = (1/2)c n³ + n;
               = c * n³ - ((1 / 2) * c * n³ - n)
               <= c * n ³(c >= 1,n >= 1)
   事实上 c 应当大于等于T(1)
   因为 T(1) = Θ(1)<= c

假设：T(n) = O(n²);

1. 猜想： T(n) = O(n²);
2. 归纳：
       T(k) <= c * k² for k < n;
3. 证明：
       T(n) = 4T(n / 2) + n
               <=4c(n / 2)² + n;
               =c * n² + n;
               =c * n² - (-n);
               <=c * n ²(不成立)(n明显大于1);
   因此假设不成立

---

1. 递归树法

举例：T(n) = T(n / 4) + T(n / 2) + n²;
    T(n) = n²
              /     \
      T(n/4)  T(n/2)
             = n²
              /     \
         (n/4)²  (n/2)²
        /     \     /     \
T(n/16)T(n/8)T(n/8)T(n/4)

计算此递归树结点总数会比较困难，但是可以肯定此递归树结点个数必定小于n(设n = 4就可以理解为什么这样)

现在计算时间复杂度
针对该递归树的第一层结点求和得出 n²
针对该递归树的第二层结点求和得出 (5 / 16)n²
针对该递归树的第三层结点求和得出 (25 / 256) n²
。。。。

所以该递归树的总的时间复杂度是：n²(1 + (5 / 16) + (5 / 16)² + ....);
所以O(n) = n^2;(忽略常数)；

---

主定理[T(n) = aT(n/b) + f(n)] (f(n) = n^c * (lgn)^k)：

分为三种情况(比较f(n)和n^logb^a的大小情况,其中n^logb^a为递归树叶节点的数量)
第1种情况：
    f(n) = O(n^logb^a-ε)[f(n) < n^logb^a]
     =>Τ(n)=Θ(n^logb^a)
第2种情况：
    f(n) = θ(n^logb^a(lgn)^k)[f(n) == n^logb^a]
     =>Τ(n)=Θ(n^logb^a(lgn)^k+1)
第3种情况：
    f(n) = Ω(n^(logb^a)+ε)[f(n) > n^logb^a]
需要条件：af(n/b)<=(1 - ε') * f(n) (ε' > 0 , ε > 0)[关于这个条件怎么理解，保持疑问]
     =>Τ(n)=Θ(f(n))

主定理应用示例：

1. T(n)=4T(n/2)+n
   n^logb^a = n²
   因为f(n) = n 小于 n^2 [符合第一种情况]
   所以T(n) = Θ(n²)

2. T(n)=4T(n/2)+n^2
   n^logb^a = n²
   因为f(n) = n² 等于 n²[符合第二种情况]
   且f(n) = n² = n² * (lgn)⁰[k此时等于0]
   所以T(n)=Θ(n²·lgn)

3. T(n)=4T(n/2)+n³
   n^logb^a = n²
   因为f(n) = n³ 大于 n²[符合第三种情况]
   所以T(n)=Θ(n³)

注意上面3个示例：a = 4,b = 2;
a是子问题的个数，b是子问题的规模。f(n)是每次额外的计算量

4. T(n)=4T(n/2) + n² / lgn;
   符合第二种情况[f(n) == Θ(n^logb^a)]：
   但是k = -1
   因为f(n) = n² / lgn = n² * (lgn)^-1
   不满足第二种情况

---

补充说明：

1 + 1/2 + 1/3 + 1/4 + ... = 2;
关于主定理的相关证明详情见算法导论公开课 日后会在博客补上