閱讀(889) 書(shū)簽贊(0) 我要糾錯(cuò)

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

2023-09-20 09:22 更新

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

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

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

// 在某運(yùn)行平臺(tái)下
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ù)以上方法，可以得到算法運(yùn)行時(shí)間為6n+12 ns ：

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

但實(shí)際上，統(tǒng)計(jì)算法的運(yùn)行時(shí)間既不合理也不現(xiàn)實(shí)。首先，我們不希望將預(yù)估時(shí)間和運(yùn)行平臺(tái)綁定，因?yàn)樗惴ㄐ枰诟鞣N不同的平臺(tái)上運(yùn)行。其次，我們很難獲知每種操作的運(yùn)行時(shí)間，這給預(yù)估過(guò)程帶來(lái)了極大的難度。

統(tǒng)計(jì)時(shí)間增長(zhǎng)趨勢(shì)

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

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

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

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

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

圖 2-7 算法 A、B 和 C 的時(shí)間增長(zhǎng)趨勢(shì)

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

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

函數(shù)漸近上界

給定一個(gè)輸入大小為 $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ù)量是一個(gè)關(guān)于輸入數(shù)據(jù)大小 n 的函數(shù)，記為 T(n) ，則以上函數(shù)的的操作數(shù)量為：

$T (n) = 3 + 2 n$

T(n) 是一次函數(shù)，說(shuō)明其運(yùn)行時(shí)間的增長(zhǎng)趨勢(shì)是線(xiàn)性的，因此它的時(shí)間復(fù)雜度是線(xiàn)性階。

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

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

函數(shù)漸近上界

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

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

函數(shù)的漸近上界

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

推算方法

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

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

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

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

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

給定一個(gè)函數(shù)，我們可以用上述技巧來(lái)統(tǒng)計(jì)操作數(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)計(jì)結(jié)果，兩者推出的時(shí)間復(fù)雜度都為 $? (?^{2})$ O(n2)。

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

=2n2+7n+3

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

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

時(shí)間復(fù)雜度由多項(xiàng)式 T(n) 中最高階的項(xiàng)來(lái)決定。這是因?yàn)樵?nbsp;n 趨于無(wú)窮大時(shí)，最高階的項(xiàng)將發(fā)揮主導(dǎo)作用，其他項(xiàng)的影響都可以被忽略。

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

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

操作數(shù)量T(n)	時(shí)間復(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)

常見(jiàn)類(lèi)型

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

圖 2-9 常見(jiàn)的時(shí)間復(fù)雜度類(lèi)型

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

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

在以下函數(shù)中，盡管操作數(shù)量 size 可能很大，但由于其與輸入數(shù)據(jù)大小 n 無(wú)關(guān)，因此時(shí)間復(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. 線(xiàn)性階 O(n)

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

time_complexity.cpp

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

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

time_complexity.cpp

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

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

3. 平方階 O(n2)

平方階的操作數(shù)量相對(duì)于輸入數(shù)據(jù)大小 n 以平方級(jí)別增長(zhǎng)。平方階通常出現(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ù)組長(zhǎng)度成平方關(guān)系
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            count++;
        }
    }
    return count;
}

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

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

以冒泡排序?yàn)槔鈱友h(huán)執(zhí)行 n?1 次，內(nèi)層循環(huán)執(zhí)行 n?1、n?2、…、2、1 次，平均為 n/2 次，因此時(shí)間復(fù)雜度為 O((n?1)n/2)=O(n2) 。

time_complexity.cpp

/* 平方階（冒泡排序） */
int bubbleSort(vector<int> &nums) {
    int count = 0; // 計(jì)數(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 個(gè)單元操作
            }
        }
    }
    return count;
}

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

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

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

time_complexity.cpp

/* 指數(shù)階（循環(huán)實(shí)現(xiàn)） */
int exponential(int n) {
    int count = 0, base = 1;
    // 細(xì)胞每輪一分為二，形成數(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ù)階的時(shí)間復(fù)雜度

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

time_complexity.cpp

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

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

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

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

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

time_complexity.cpp

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

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

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

time_complexity.cpp

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

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

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

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

屏幕截圖 2023-09-14 133707

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

6. 線(xiàn)性對(duì)數(shù)階 O(n log ?n)

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

time_complexity.cpp

/* 線(xiàn)性對(duì)數(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 展示了線(xiàn)性對(duì)數(shù)階的生成方式。二叉樹(shù)的每一層的操作總數(shù)都為 n $?$ ，樹(shù)共有l(wèi)og2 n+1層，因此時(shí)間復(fù)雜度為 O(n log n) $? (? \log ? ?)$ 。

圖 2-13 線(xiàn)性對(duì)數(shù)階的時(shí)間復(fù)雜度

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

7. 階乘階 O(n!)

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

屏幕截圖 2023-09-14 135757

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

time_complexity.cpp

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

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

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

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

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

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

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

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

worst_best_time_complexity.cpp

/* 生成一個(gè)數(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)時(shí)間生成隨機(jī)種子
    unsigned seed = chrono::system_clock::now().time_since_epoch().count();
    // 隨機(jī)打亂數(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ù)組頭部時(shí)，達(dá)到最佳時(shí)間復(fù)雜度 O(1)
        // 當(dāng)元素 1 在數(shù)組尾部時(shí)，達(dá)到最差時(shí)間復(fù)雜度 O(n)
        if (nums[i] == 1)
            return i;
    }
    return -1;
}

值得說(shuō)明的是，我們?cè)趯?shí)際中很少使用最佳時(shí)間復(fù)雜度，因?yàn)橥ǔＶ挥性诤苄「怕氏虏拍苓_(dá)到，可能會(huì)帶來(lái)一定的誤導(dǎo)性。而最差時(shí)間復(fù)雜度更為實(shí)用，因?yàn)樗o出了一個(gè)效率安全值，讓我們可以放心地使用算法。

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

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

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

為什么很少看到 Θ 符號(hào)？

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

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

← C++迭代與遞歸

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

寫(xiě)筆記

我要補(bǔ)充

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

統(tǒng)計(jì)時(shí)間增長(zhǎng)趨勢(shì)

函數(shù)漸近上界

推算方法

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

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

常見(jiàn)類(lèi)型

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

2. 線(xiàn)性階 O(n)

3. 平方階 O(n2)

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

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

6. 線(xiàn)性對(duì)數(shù)階 O(n log ?n)

7. 階乘階 O(n!)

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

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