分类 Math 下的文章

本文采用知识共享 署名-相同方式共享 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³)

Title - Artist
0:00