大神的世界

在Lec02最後面我們談論了時間複雜度的定義
接下來，我們要來討論一些規則

Rule 1:
    考慮一個由兩個程序所構成的程式，這兩個程序分別為 procedure A 和 procedure B
    且 procedure A 共需執行 T1(N) 道指令 ， procedure B 共需執行 T2(N) 道指令
    並假設，T1(N) = O( f(N) ) , T2(N) = O( g(N) )
    請問，這支程式執行所需的總指令數為何？
    是 T1(N) + T2(N)  還是 T1(N) * T2(N)
    答： 視情況而定

    若程序A和程序B互相獨立且依序執行，則總指令數為T1(N) + T2(N)
    在這情況下，這支程式的時間複雜度為 max( O(f(N)) , O(g(N)) )

    若程序A會呼叫程序B，則總指令數最多可到 T1(N)*T2(N)
    在這情況下，這支程式的時間複雜度為 O( f(N)*g(N) )

Rule 2:
    若 T（N） 為 k 次多項式
    則 T（N） = Θ ( Nk)   (令 c = T(N) 的首項係數 + 1)

Rule 3:
    (logN)k = O(N)
 
    令 N = 2k
    => log N = k log2 <= k x (2k)1/k = k x N1/k
    =>  ( log N)k <= kk x N   (c = kk ,  n0 = 1)

接下來，來討論些比較特殊的例子

1. if / else
    計算時間複雜度須以最大執行數為考量，例如

    if( i > 0 )
    { i++, j++;}
    else{
    for(j = 0; j<N; j++) k++; }

    complexity = max( 1(個人覺得是1), N） = N

2. recursive

    long int F (int N）
    {
       if(N <= 1)
          return 1;
      else
          return N*F(N-1);
    }  

    則： T(N) = T(N-1) + c  (c 是一個 constant）
    
    令 T(N) = aN
    => aN = aN-1 + c
    
    因為 aN-1(a - 1) = 0
    => a = 1
    => T(N) (h) = 1

    再令  T(N) = dN
    => dN = d(N-1) + c
    => d = c
    => T（N）(p) = cN
    => T(N) = cN + 1 = O(N)

     T(N) = T(N-1) + T(N-2) + c
     => a2 - a - 1 = 0
     => a = (1 + sqrt(5)) / 2
     => T(N) (h) = [ (1 + sqrt(5) ) / 2 ]N
   
     令 T(N) = d
      => d = -c
      => T(N) (p) = -c
      => T(N) = [ (1 + sqrt(5) ) / 2 ]N - c = O（2N)

時間複雜度大致可區分成以下幾種 (快到慢)

1. c： 常數時間 （constatnt time)
2. logN: 對數時間（Logarithmic time) 、 以2為底數： 次線性時間（sub-linear time)
3. log2N: 對數平方時間（Log-squared time)
4. N: 線性時間 （linear time)
5. N logN: 線性對數時間
6. N2： 平方時間（quadratic time)
7.N3: 立方時間（cubic time)
8.2n: 指數時間（exponential time)