閱讀(1.2k) 書簽贊(0) 我要糾錯

C++時間復(fù)雜度

2023-09-20 09:22 更新

運行時間可以直觀且準(zhǔn)確地反映算法的效率。如果我們想要準(zhǔn)確預(yù)估一段代碼的運行時間，應(yīng)該如何操作呢？

確定運行平臺，包括硬件配置、編程語言、系統(tǒng)環(huán)境等，這些因素都會影響代碼的運行效率。
評估各種計算操作所需的運行時間，例如加法操作 + 需要 1 ns，乘法操作 * 需要 10 ns，打印操作 print() 需要 5 ns 等。
統(tǒng)計代碼中所有的計算操作，并將所有操作的執(zhí)行時間求和，從而得到運行時間。

例如在以下代碼中，輸入數(shù)據(jù)大小為 $n$ ：

// 在某運行平臺下
void algorithm(int n) {
    int a = 2;  // 1 ns
    a = a + 1;  // 1 ns
    a = a * 2;  // 10 ns
    // 循環(huán) n 次
    for (int i = 0; i < n; i++) {  // 1 ns ，每輪都要執(zhí)行 i++
        cout << 0 << endl;         // 5 ns
    }
}

根據(jù)以上方法，可以得到算法運行時間為6n+12 ns ：

$1 + 1 + 10 + (1 + 5) \times n = 6 n + 12$

但實際上，統(tǒng)計算法的運行時間既不合理也不現(xiàn)實。首先，我們不希望將預(yù)估時間和運行平臺綁定，因為算法需要在各種不同的平臺上運行。其次，我們很難獲知每種操作的運行時間，這給預(yù)估過程帶來了極大的難度。

統(tǒng)計時間增長趨勢

時間復(fù)雜度分析統(tǒng)計的不是算法運行時間，而是算法運行時間隨著數(shù)據(jù)量變大時的增長趨勢。

“時間增長趨勢”這個概念比較抽象，我們通過一個例子來加以理解。假設(shè)輸入數(shù)據(jù)大小為 $n$ ，給定三個算法函數(shù) A、B 和 C ：

// 算法 A 的時間復(fù)雜度：常數(shù)階
void algorithm_A(int n) {
    cout << 0 << endl;
}
// 算法 B 的時間復(fù)雜度：線性階
void algorithm_B(int n) {
    for (int i = 0; i < n; i++) {
        cout << 0 << endl;
    }
}
// 算法 C 的時間復(fù)雜度：常數(shù)階
void algorithm_C(int n) {
    for (int i = 0; i < 1000000; i++) {
        cout << 0 << endl;
    }
}

圖 2-7 展示了以上三個算法函數(shù)的時間復(fù)雜度。

算法 A 只有 1 個打印操作，算法運行時間不隨著 n 增大而增長。我們稱此算法的時間復(fù)雜度為“常數(shù)階”。
算法 B 中的打印操作需要循環(huán) ? 次，算法運行時間隨著 n 增大呈線性增長。此算法的時間復(fù)雜度被稱為“線性階”。
算法 C 中的打印操作需要循環(huán) 1000000 次，雖然運行時間很長，但它與輸入數(shù)據(jù)大小 n 無關(guān)。因此 C 的時間復(fù)雜度和 A 相同，仍為“常數(shù)階”。

圖 2-7 算法 A、B 和 C 的時間增長趨勢

相較于直接統(tǒng)計算法運行時間，時間復(fù)雜度分析有哪些特點呢？

時間復(fù)雜度能夠有效評估算法效率。例如，算法 B 的運行時間呈線性增長，在 n>1 時比算法 A 更慢，在 n>1000000 時比算法 C 更慢。事實上，只要輸入數(shù)據(jù)大小 ? 足夠大，復(fù)雜度為“常數(shù)階”的算法一定優(yōu)于“線性階”的算法，這正是時間增長趨勢所表達的含義。
時間復(fù)雜度的推算方法更簡便。顯然，運行平臺和計算操作類型都與算法運行時間的增長趨勢無關(guān)。因此在時間復(fù)雜度分析中，我們可以簡單地將所有計算操作的執(zhí)行時間視為相同的“單位時間”，從而將“計算操作的運行時間的統(tǒng)計”簡化為“計算操作的數(shù)量的統(tǒng)計”，這樣以來估算難度就大大降低了。
時間復(fù)雜度也存在一定的局限性。例如，盡管算法 A 和 C 的時間復(fù)雜度相同，但實際運行時間差別很大。同樣，盡管算法 B 的時間復(fù)雜度比 C 高，但在輸入數(shù)據(jù)大小 n 較小時，算法 B 明顯優(yōu)于算法 C 。在這些情況下，我們很難僅憑時間復(fù)雜度判斷算法效率的高低。當(dāng)然，盡管存在上述問題，復(fù)雜度分析仍然是評判算法效率最有效且常用的方法。

函數(shù)漸近上界

給定一個輸入大小為 $n$ 的函數(shù)：

void algorithm(int n) {
    int a = 1;  // +1
    a = a + 1;  // +1
    a = a * 2;  // +1
    // 循環(huán) n 次
    for (int i = 0; i < n; i++) { // +1（每輪都執(zhí)行 i ++）
        cout << 0 << endl;    // +1
    }
}

設(shè)算法的操作數(shù)量是一個關(guān)于輸入數(shù)據(jù)大小 n 的函數(shù)，記為 T(n) ，則以上函數(shù)的的操作數(shù)量為：

$T (n) = 3 + 2 n$

T(n) 是一次函數(shù)，說明其運行時間的增長趨勢是線性的，因此它的時間復(fù)雜度是線性階。

我們將線性階的時間復(fù)雜度記為 O(n) ，這個數(shù)學(xué)符號稱為「大 O 記號 big-O notation」，表示函數(shù) T(n) 的「漸近上界 asymptotic upper bound」。

時間復(fù)雜度分析本質(zhì)上是計算“操作數(shù)量函數(shù) T(n)”的漸近上界，其具有明確的數(shù)學(xué)定義。

函數(shù)漸近上界

若存在正實數(shù)c 和實數(shù) $n_{0}$ ，使得對于所有的 $n > n_{0}$ ，均有 $T (n) \leq c ? f (n)$ ，則可認為 $f (n)$ 給出了 $T (n)$ 的一個漸近上界，記為 $T (n) = O (f (n))$ 。

如圖 2-8 所示，計算漸近上界就是尋找一個函數(shù) f(n) ，使得當(dāng) n 趨向于無窮大時，T(n) 和 f(n) 處于相同的增長級別，僅相差一個常數(shù)項 c 的倍數(shù)。

函數(shù)的漸近上界

圖 2-8 函數(shù)的漸近上界

推算方法

漸近上界的數(shù)學(xué)味兒有點重，如果你感覺沒有完全理解，也無須擔(dān)心。因為在實際使用中，我們只需要掌握推算方法，數(shù)學(xué)意義就可以逐漸領(lǐng)悟。

根據(jù)定義，確定 f(n) 之后，我們便可得到時間復(fù)雜度 O(f(n)) 。那么如何確定漸近上界 f(n) 呢？總體分為兩步：首先統(tǒng)計操作數(shù)量，然后判斷漸近上界。

1. 第一步：統(tǒng)計操作數(shù)量

針對代碼，逐行從上到下計算即可。然而，由于上述 c?f(n) 中的常數(shù)項 c 可以取任意大小，因此操作數(shù)量 T(n) 中的各種系數(shù)、常數(shù)項都可以被忽略。根據(jù)此原則，可以總結(jié)出以下計數(shù)簡化技巧。

忽略 T(n) 中的常數(shù)項。因為它們都與 n 無關(guān)，所以對時間復(fù)雜度不產(chǎn)生影響。
省略所有系數(shù)。例如，循環(huán) 2n 次、5n+1 次等，都可以簡化記為 n 次，因為 n 前面的系數(shù)對時間復(fù)雜度沒有影響。
循環(huán)嵌套時使用乘法?？偛僮鲾?shù)量等于外層循環(huán)和內(nèi)層循環(huán)操作數(shù)量之積，每一層循環(huán)依然可以分別套用第 1. 點和第 2. 點的技巧。

給定一個函數(shù)，我們可以用上述技巧來統(tǒng)計操作數(shù)量。

void algorithm(int n) {
    int a = 1;  // +0（技巧 1）
    a = a + n;  // +0（技巧 1）
    // +n（技巧 2）
    for (int i = 0; i < 5 * n + 1; i++) {
        cout << 0 << endl;
    }
    // +n*n（技巧 3）
    for (int i = 0; i < 2 * n; i++) {
        for (int j = 0; j < n + 1; j++) {
            cout << 0 << endl;
        }
    }
}

以下公式展示了使用上述技巧前后的統(tǒng)計結(jié)果，兩者推出的時間復(fù)雜度都為 $? (?^{2})$ O(n2)。

T(n)=2n(n+1)+(5n+1)+2 完整統(tǒng)計(-.-|||)

=2n2+7n+3

T(n)=n2+n 偷懶統(tǒng)計(o.O)

2. 第二步：判斷漸近上界

時間復(fù)雜度由多項式 T(n) 中最高階的項來決定。這是因為在 n 趨于無窮大時，最高階的項將發(fā)揮主導(dǎo)作用，其他項的影響都可以被忽略。

表 2-2 展示了一些例子，其中一些夸張的值是為了強調(diào)“系數(shù)無法撼動階數(shù)”這一結(jié)論。當(dāng) n 趨于無窮大時，這些常數(shù)變得無足輕重。

表 2-2 不同操作數(shù)量對應(yīng)的時間復(fù)雜度

操作數(shù)量T(n)	時間復(fù)雜度O(f(n))
100000	O(1)
3n+2	O(n)
2n2+3n+2	O(n2)
n3+10000n2	O(n3)
22+10000n¹⁰⁰⁰⁰	O(2^n)

常見類型

設(shè)輸入數(shù)據(jù)大小為 $?$ ，常見的時間復(fù)雜度類型如圖 2-9 所示（按照從低到高的順序排列）。

圖 2-9 常見的時間復(fù)雜度類型

1. 常數(shù)階 O(1)

常數(shù)階的操作數(shù)量與輸入數(shù)據(jù)大小 n 無關(guān)，即不隨著 n 的變化而變化。

在以下函數(shù)中，盡管操作數(shù)量 size 可能很大，但由于其與輸入數(shù)據(jù)大小 n 無關(guān)，因此時間復(fù)雜度仍為 O(1) ：

time_complexity.cpp

/* 常數(shù)階 */
int constant(int n) {
    int count = 0;
    int size = 100000;
    for (int i = 0; i < size; i++)
        count++;
    return count;
}

2. 線性階 O(n)

線性階的操作數(shù)量相對于輸入數(shù)據(jù)大小 n 以線性級別增長。線性階通常出現(xiàn)在單層循環(huán)中：

time_complexity.cpp

/* 線性階 */
int linear(int n) {
    int count = 0;
    for (int i = 0; i < n; i++)
        count++;
    return count;
}

遍歷數(shù)組和遍歷鏈表等操作的時間復(fù)雜度均為O(n)，其中n為數(shù)組或鏈表的長度：

time_complexity.cpp

/* 線性階（遍歷數(shù)組） */
int arrayTraversal(vector<int> &nums) {
    int count = 0;
    // 循環(huán)次數(shù)與數(shù)組長度成正比
    for (int num : nums) {
        count++;
    }
    return count;
}

值得注意的是，輸入數(shù)據(jù)大小n需根據(jù)輸入數(shù)據(jù)的類型來具體確定。比如在第一個示例中，變量n為輸入數(shù)據(jù)大??；在第二個示例中，數(shù)組長度n為數(shù)據(jù)大小。

3. 平方階 O(n2)

平方階的操作數(shù)量相對于輸入數(shù)據(jù)大小 n 以平方級別增長。平方階通常出現(xiàn)在嵌套循環(huán)中，外層循環(huán)和內(nèi)層循環(huán)都為 O(n) ，因此總體為 O(n2) ：

time_complexity.cpp

/* 平方階 */
int quadratic(int n) {
    int count = 0;
    // 循環(huán)次數(shù)與數(shù)組長度成平方關(guān)系
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            count++;
        }
    }
    return count;
}

圖 2-10 對比了常數(shù)階、線性階和平方階三種時間復(fù)雜度。

圖 2-10 常數(shù)階、線性階和平方階的時間復(fù)雜度

以冒泡排序為例，外層循環(huán)執(zhí)行 n?1 次，內(nèi)層循環(huán)執(zhí)行 n?1、n?2、…、2、1 次，平均為 n/2 次，因此時間復(fù)雜度為 O((n?1)n/2)=O(n2) 。

time_complexity.cpp

/* 平方階（冒泡排序） */
int bubbleSort(vector<int> &nums) {
    int count = 0; // 計數(shù)器
    // 外循環(huán)：未排序區(qū)間為 [0, i]
    for (int i = nums.size() - 1; i > 0; i--) {
        // 內(nèi)循環(huán)：將未排序區(qū)間 [0, i] 中的最大元素交換至該區(qū)間的最右端
        for (int j = 0; j < i; j++) {
            if (nums[j] > nums[j + 1]) {
                // 交換 nums[j] 與 nums[j + 1]
                int tmp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = tmp;
                count += 3; // 元素交換包含 3 個單元操作
            }
        }
    }
    return count;
}

4. 指數(shù)階 O(2^n)

生物學(xué)的“細胞分裂”是指數(shù)階增長的典型例子：初始狀態(tài)為 1 個細胞，分裂一輪后變?yōu)?nbsp;2 個，分裂兩輪后變?yōu)?nbsp;4 個，以此類推，分裂 n 輪后有 2^n 個細胞。

圖 2-11 和以下代碼模擬了細胞分裂的過程，時間復(fù)雜度為 O(2^n) 。

time_complexity.cpp

/* 指數(shù)階（循環(huán)實現(xiàn)） */
int exponential(int n) {
    int count = 0, base = 1;
    // 細胞每輪一分為二，形成數(shù)列 1, 2, 4, 8, ..., 2^(n-1)
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < base; j++) {
            count++;
        }
        base *= 2;
    }
    // count = 1 + 2 + 4 + 8 + .. + 2^(n-1) = 2^n - 1
    return count;
}

圖 2-11 指數(shù)階的時間復(fù)雜度

在實際算法中，指數(shù)階常出現(xiàn)于遞歸函數(shù)中。例如在以下代碼中，其遞歸地一分為二，經(jīng)過 n 次分裂后停止：

time_complexity.cpp

/* 指數(shù)階（遞歸實現(xiàn)） */
int expRecur(int n) {
    if (n == 1)
        return 1;
    return expRecur(n - 1) + expRecur(n - 1) + 1;
}

指數(shù)階增長非常迅速，在窮舉法（暴力搜索、回溯等）中比較常見。對于數(shù)據(jù)規(guī)模較大的問題，指數(shù)階是不可接受的，通常需要使用動態(tài)規(guī)劃或貪心等算法來解決。

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

與指數(shù)階相反，對數(shù)階反映了“每輪縮減到一半”的情況。設(shè)輸入數(shù)據(jù)大小為 n ，由于每輪縮減到一半，因此循環(huán)次數(shù)是 log2?? ，即 2? 的反函數(shù)。

圖 2-12 和以下代碼模擬了“每輪縮減到一半”的過程，時間復(fù)雜度為 O(log2? n) ，簡記為 O(log? n) 。

time_complexity.cpp

/* 對數(shù)階（循環(huán)實現(xiàn)） */
int logarithmic(float n) {
    int count = 0;
    while (n > 1) {
        n = n / 2;
        count++;
    }
    return count;
}

圖 2-12 對數(shù)階的時間復(fù)雜度

與指數(shù)階類似，對數(shù)階也常出現(xiàn)于遞歸函數(shù)中。以下代碼形成了一個高度為 log2? n 的遞歸樹：

time_complexity.cpp

/* 對數(shù)階（遞歸實現(xiàn)） */
int logRecur(float n) {
    if (n <= 1)
        return 0;
    return logRecur(n / 2) + 1;
}

對數(shù)階常出現(xiàn)于基于分治策略的算法中，體現(xiàn)了“一分為多”和“化繁為簡”的算法思想。它增長緩慢，是僅次于常數(shù)階的理想的時間復(fù)雜度。

O(log? n) 的底數(shù)是多少？

準(zhǔn)確來說，“一分為m $?$ ”對應(yīng)的時間復(fù)雜度是O(logm n) $? (\log_{?} ? ?)$ 。而通過對數(shù)換底公式，我們可以得到具有不同底數(shù)的、相等的時間復(fù)雜度：

屏幕截圖 2023-09-14 133707

也就是說，底數(shù) m 可以在不影響復(fù)雜度的前提下轉(zhuǎn)換。因此我們通常會省略底數(shù) m $?$ ，將對數(shù)階直接記為 O(log n) $? (\log ? ?)$ 。

6. 線性對數(shù)階 O(n log ?n)

線性對數(shù)階常出現(xiàn)于嵌套循環(huán)中，兩層循環(huán)的時間復(fù)雜度分別為 O(log? n) 和 O(n) 。相關(guān)代碼如下：

time_complexity.cpp

/* 線性對數(shù)階 */
int linearLogRecur(float n) {
    if (n <= 1)
        return 1;
    int count = linearLogRecur(n / 2) + linearLogRecur(n / 2);
    for (int i = 0; i < n; i++) {
        count++;
    }
    return count;
}

圖 2-13 展示了線性對數(shù)階的生成方式。二叉樹的每一層的操作總數(shù)都為 n $?$ ，樹共有l(wèi)og2 n+1層，因此時間復(fù)雜度為 O(n log n) $? (? \log ? ?)$ 。

圖 2-13 線性對數(shù)階的時間復(fù)雜度

主流排序算法的時間復(fù)雜度通常為 O(n log? n) ，例如快速排序、歸并排序、堆排序等。

7. 階乘階 O(n!)

階乘階對應(yīng)數(shù)學(xué)上的“全排列”問題。給定 $?$ n 個互不重復(fù)的元素，求其所有可能的排列方案，方案數(shù)量為：

屏幕截圖 2023-09-14 135757

階乘通常使用遞歸實現(xiàn)。如圖 2-14 和以下代碼所示，第一層分裂出n個，第二層分裂出 n-1 $? ? 1$ 個，以此類推，直至第 $?$ 層時停止分裂：

time_complexity.cpp

/* 階乘階（遞歸實現(xiàn)） */
int factorialRecur(int n) {
    if (n == 0)
        return 1;
    int count = 0;
    // 從 1 個分裂出 n 個
    for (int i = 0; i < n; i++) {
        count += factorialRecur(n - 1);
    }
    return count;
}

階乘階的時間復(fù)雜度

圖 2-14 階乘階的時間復(fù)雜度

請注意，因為當(dāng) n≥4 時恒有 n!>2^n ，所以階乘階比指數(shù)階增長得更快，在 n 較大時也是不可接受的。

最差、最佳、平均時間復(fù)雜度

算法的時間效率往往不是固定的，而是與輸入數(shù)據(jù)的分布有關(guān)。假設(shè)輸入一個長度為 n 的數(shù)組 nums ，其中 nums 由從 1 至 n 的數(shù)字組成，每個數(shù)字只出現(xiàn)一次；但元素順序是隨機打亂的，任務(wù)目標(biāo)是返回元素 1 的索引。我們可以得出以下結(jié)論。

當(dāng) nums = [?, ?, ..., 1] ，即當(dāng)末尾元素是 1 時，需要完整遍歷數(shù)組，達到最差時間復(fù)雜度 O(n) 。
當(dāng) nums = [1, ?, ?, ...] ，即當(dāng)首個元素為 1 時，無論數(shù)組多長都不需要繼續(xù)遍歷，達到最佳時間復(fù)雜度 Ω(1) 。

“最差時間復(fù)雜度”對應(yīng)函數(shù)漸近上界，使用大 O 記號表示。相應(yīng)地，“最佳時間復(fù)雜度”對應(yīng)函數(shù)漸近下界，用 Ω 記號表示：

worst_best_time_complexity.cpp

/* 生成一個數(shù)組，元素為 { 1, 2, ..., n }，順序被打亂 */
vector<int> randomNumbers(int n) {
    vector<int> nums(n);
    // 生成數(shù)組 nums = { 1, 2, 3, ..., n }
    for (int i = 0; i < n; i++) {
        nums[i] = i + 1;
    }
    // 使用系統(tǒng)時間生成隨機種子
    unsigned seed = chrono::system_clock::now().time_since_epoch().count();
    // 隨機打亂數(shù)組元素
    shuffle(nums.begin(), nums.end(), default_random_engine(seed));
    return nums;
}

/* 查找數(shù)組 nums 中數(shù)字 1 所在索引 */
int findOne(vector<int> &nums) {
    for (int i = 0; i < nums.size(); i++) {
        // 當(dāng)元素 1 在數(shù)組頭部時，達到最佳時間復(fù)雜度 O(1)
        // 當(dāng)元素 1 在數(shù)組尾部時，達到最差時間復(fù)雜度 O(n)
        if (nums[i] == 1)
            return i;
    }
    return -1;
}

值得說明的是，我們在實際中很少使用最佳時間復(fù)雜度，因為通常只有在很小概率下才能達到，可能會帶來一定的誤導(dǎo)性。而最差時間復(fù)雜度更為實用，因為它給出了一個效率安全值，讓我們可以放心地使用算法。

從上述示例可以看出，最差或最佳時間復(fù)雜度只出現(xiàn)于“特殊的數(shù)據(jù)分布”，這些情況的出現(xiàn)概率可能很小，并不能真實地反映算法運行效率。相比之下，平均時間復(fù)雜度可以體現(xiàn)算法在隨機輸入數(shù)據(jù)下的運行效率，用 Θ 記號來表示。

對于部分算法，我們可以簡單地推算出隨機數(shù)據(jù)分布下的平均情況。比如上述示例，由于輸入數(shù)組是被打亂的，因此元素 1 出現(xiàn)在任意索引的概率都是相等的，那么算法的平均循環(huán)次數(shù)就是數(shù)組長度的一半 n/2 ，平均時間復(fù)雜度為 Θ(n/2)=Θ(n) 。

但對于較為復(fù)雜的算法，計算平均時間復(fù)雜度往往是比較困難的，因為很難分析出在數(shù)據(jù)分布下的整體數(shù)學(xué)期望。在這種情況下，我們通常使用最差時間復(fù)雜度作為算法效率的評判標(biāo)準(zhǔn)。

為什么很少看到 Θ 符號？

可能由于 O 符號過于朗朗上口，我們常常使用它來表示平均時間復(fù)雜度。但從嚴格意義上看，這種做法并不規(guī)范。在本書和其他資料中，若遇到類似“平均時間復(fù)雜度 O(n)”的表述，請將其直接理解為 Θ(n) 。

以上內(nèi)容是否對您有幫助：

← C++迭代與遞歸

C++空間復(fù)雜度 →

寫筆記

我要補充

C++時間復(fù)雜度

統(tǒng)計時間增長趨勢

函數(shù)漸近上界

推算方法

1. 第一步：統(tǒng)計操作數(shù)量

2. 第二步：判斷漸近上界

常見類型

1. 常數(shù)階 O(1)

2. 線性階 O(n)

3. 平方階 O(n2)

4. 指數(shù)階 O(2^n)

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

6. 線性對數(shù)階 O(n log ?n)

7. 階乘階 O(n!)

最差、最佳、平均時間復(fù)雜度

最差、最佳、平均時間復(fù)雜度