時間頻度：

一個算法花費(fèi)的時間與算法中語句的執(zhí)行次數(shù)成正比，我們將算法中的語句執(zhí)行次數(shù)稱為語句頻度或時間頻度，記為T(n)，n稱為問題的規(guī)模.

在時間頻度中，當(dāng)n不斷變化時，時間頻度T(n)也會不斷變化，但有時我們想知道隨著問題的規(guī)模n的不斷增加，運(yùn)行時間呈現(xiàn)怎樣的變化規(guī)律，為此，引入了時間復(fù)雜度.

時間復(fù)雜度：

• 一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)，用T(n)表示，若有某個輔助函數(shù)f(n)，使得當(dāng)n趨近于無窮大時，T(n)/f(n)的極限值為不等于零的常數(shù)，則稱f(n)是T(n)的同數(shù)量級函數(shù)。記作T(n) = O(f(n))，稱O(f(n))為算法的時間復(fù)雜度.
• 數(shù)學(xué)上定義：存在大于0的常數(shù)C和非負(fù)整數(shù)n'，使得對于任意的n >= n'來說，T(n) <= C * f(n)，表示為T(n) = O(f(n));
• 簡單來說：
  O(n2)表示當(dāng)n很大的時候，復(fù)雜度約等于C * n2，C是某個常數(shù);
  O(n)是說n很大的時候復(fù)雜度約等于C * n，C是某個常數(shù).
• 例如，O(2n2 + n + 1) = O (3n2 + n + 3) = O (7n2 + n) = O(n2)，一般都只用O(n2)表示就可以了.

時間復(fù)雜度n2比對

圖中4條曲線分別表示4種不同的執(zhí)行次數(shù)表達(dá)式，從圖中可以看出，只要最高項(xiàng)的階數(shù)相同，4種表達(dá)式值受其他項(xiàng)的影響很小，隨著n增大，幾乎可以忽略不計，甚至可以忽略與最高項(xiàng)相乘的常數(shù)

更通俗的講：時間復(fù)雜度是T(n)中受n的變化影響最大的那一項(xiàng)(不包含系數(shù))

最壞時間復(fù)雜度和平均時間復(fù)雜度

最壞情況下的時間復(fù)雜度稱最壞時間復(fù)雜度。一般不特別說明，討論的時間復(fù)雜度均是最壞情況下的時間復(fù)雜度。 這樣做的原因是：最壞情況下的時間復(fù)雜度是算法在任何輸入實(shí)例上運(yùn)行時間的上界，這就保證了算法的運(yùn)行時間不會超過此時間.

常見時間復(fù)雜度

常數(shù)階O(1)、對數(shù)階O(log?n)、線性階O(n)、線性對數(shù)階O(nlog?n)、平方階O(n2)、立方階O(n3)、k次方階(n)、指數(shù)階O(2?)

常見時間復(fù)雜度比對圖

從圖中不難看出，選擇算法時候應(yīng)該盡量選擇對數(shù)階而非指數(shù)階時間復(fù)雜度的算法.

常數(shù)階O(1)

void func(int n) {
    printf("Hello, World!\n"); // 循環(huán)體時間復(fù)雜度為 O(1)
}

對數(shù)階O(log?n)

void func(int n) {
    for(int i = 1; i < n; i *= 2) { // 循環(huán)次數(shù)為 log?n
        printf("Hello, World!\n"); // 循環(huán)體時間復(fù)雜度為 O(log?n)
    }
}

線性階O(n)

void func(int n) {
    for(int i = 0; i < n; i++) { // 循環(huán)次數(shù)為 n
        printf("Hello, World!\n"); // 循環(huán)體時間復(fù)雜度為 O(n)
    }
}

線性對數(shù)階O(nlog?n)

void func(int n) {
    for(int i = 0; i < n; i++) { // 循環(huán)次數(shù)為 n
        for(int j = 1; j < n; j *= 2) { // 循環(huán)次數(shù)為 log?n
            printf("Hello, World!\n"); // 循環(huán)體時間復(fù)雜度為 O(nlog?n)
        }
    }
}

平方階O(n2)

void func(int n) {
    for(int i = 0; i < n; i++) { // 循環(huán)次數(shù)為 n
        for(int j = 0; j < n; j++) { // 循環(huán)次數(shù)為 n
            printf("Hello, World!\n"); // 循環(huán)體時間復(fù)雜度為 O(n2)
        }
    }
}