大O符號表示法

又稱算法的漸進時間/空間復雜度，它不是用于反應算法真實的執(zhí)行時間/空間的，而是用來表示代碼執(zhí)行時間/空間的增長變化趨勢。

常見的時間復雜度量級

• 常數(shù)階O(1)
• 對數(shù)階O(logN)
• 線性階O(n)
• 線性對數(shù)階O(nlogN)
• 平方階O(n2)
• 立方階O(n3)
• K次方階O(n^k)
• 指數(shù)階(2^n)

O(n) 模型

for(int i=0;i<n;i++){
  //todo
}

O(logN) 模型

for(int i=0;i<n;i*=2){
  //todo
}

假設(shè)x為循環(huán)次數(shù)，有2^x=n，即x = log₂n

O(nlogN)模型

將O(logN) 模型循環(huán)n遍

for(int i=0; i<n; i++){
  for(int j=0; j<n; j*=2){
    //todo
  }
}

O(n2)模型

將O(n) 模型循環(huán)n遍

for(int i=0; i<n; i++){
  for(int j=0; j<n; j++){
    //todo
  }
}

O(2^n)模型

long aFunc(int n) {    
    if (n <= 1) {        
        return 1;
    } else {        
        return aFunc(n - 1) + aFunc(n - 2);
    }
}

顯然運行次數(shù)，T(0) = T(1) = 1，同時 T(n) = T(n - 1) + T(n - 2) + 1，這里的 1 是其中的加法算一次執(zhí)行。顯然 T(n) = T(n - 1) + T(n - 2) 是一個斐波那契數(shù)列，通過歸納證明法可以證明，當 n >= 1 時 T(n) < (5/3)^n，同時當 n > 4 時 T(n) >= (3/2)^n。 所以該方法的時間復雜度可以表示為 O((5/3)^n)，簡化后為 O(2^n)。

空間復雜度（略）