本文采用知识共享 署名-相同方式共享 4.0 国际 许可协议进行许可。
访问 https://creativecommons.org/licenses/by-sa/4.0/ 查看该许可协议。

代换法解(Substitution method)upper bounds

1. Guess the form of the solution.
2. Verify by induction.
3. Solve for constants.
   Example: T(n) = 4T(n/2) + n

   Inductive hypothesis: T(k) ≤ c1k2 – c2k for k < n.
        T(n) = 4T(n/2) + n
            = 4(c1(n/2)2 – c2(n/2)) + n
            = c1n2 – 2c2n + n
            = c1n2 – c2n – (c2n – n)
            ≤ c1n2 – c2n if c2 ≥ 1.

   递归树法(Recursion-tree method)解upper bounds

   Example: T(n) = T(n/4) + T(n/2) + 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²(1 + 5/16 + (5/16)² + (5/16)³ + ...)
             = Θ(n²) // ignore consts
   ```text              
   #### 主方法(Master method)解upper bounds
   T(n) = aT(n/b) + f(n), where a>=1, b>1, and f is asymptotically positive.
   case1:
   ```text
   Compare f(n) with nlogba:
   f(n) = O(n^(logba–ε)) for some constant ε > 0.
   • f(n) grows polynomially slower than nlogba(by an nε factor).
   => T(n) = Θ(n^(logba)).

   case2:

   f(n) = Θ(n^(logba)*lgn) for some constant k ≥ 0.
   • f(n) and n(logba) grow at similar rates.
   => T(n) = Θ(n^(logba) lgn).

   case3:

   f(n) = Ω(n^(logba)+ε) for some constant ε > 0.
   • f(n) grows polynomially faster than nlogba (by
   an nε factor),
   and f(n) satisfies the regularity condition that
   af(n/b) ≤ cf(n) for some constant c < 1.
   => T(n) = Θ(f(n)).

   Example1: T(n) = 4T(n/2) + n
   n^(logba–1) = n, case1, Result: Θ(n^(logba))

Example2: T(n) = 4T(n/2) + n²
n^(logba) = n², case2, Result: Θ(n^(logba) * lgn)

Example3: T(n) = 4T(n/2) + n³
n^(logba+1) = n³, case3, Result: Θ(n³)