使用 JavaScript 時(shí)，編寫(xiě)函數(shù)式代碼很重要，但確保其高效運(yùn)行也同樣重要。這就是 Big O 表示法的用武之地。它提供了一種方法來(lái)分析代碼的性能如何隨著輸入大小的增加而擴(kuò)展，從而幫助您編寫(xiě)優(yōu)化且可擴(kuò)展的應(yīng)用程序。

本文將通過(guò) JavaScript 中適合初學(xué)者的示例探索 Big O 表示法和常見(jiàn)時(shí)間復(fù)雜度的基礎(chǔ)知識(shí)

什么是大 O 表示法？

大O表示法是描述算法效率的數(shù)學(xué)表示形式。它幫助我們理解：

1. 時(shí)間復(fù)雜度：算法的執(zhí)行時(shí)間如何隨輸入大小的變化而變化。
2. 空間復(fù)雜度：算法的內(nèi)存使用量如何隨輸入大小的變化而變化。

目標(biāo)是評(píng)估算法隨著輸入大小的增長(zhǎng)而表現(xiàn)如何，重點(diǎn)關(guān)注最壞的情況。

---

為什么大 O 表示法很重要？

假設(shè)您的任務(wù)是在電話(huà)簿中查找姓名：

• 一種方法是翻閱每一頁(yè)，直到找到名稱(chēng)（線性搜索）。
• 另一種是從中間開(kāi)始，系統(tǒng)地縮小范圍（二分查找）。

兩種方法都可以解決問(wèn)題，但是隨著電話(huà)簿大小的增長(zhǎng)，它們的效率差異很大。 Big O 幫助我們比較這些方法并選擇最好的一種。

---

大 O 表示法的實(shí)際應(yīng)用

下面是常見(jiàn)的 Big O 復(fù)雜性，并通過(guò) JavaScript 中的實(shí)際示例進(jìn)行了解釋。

---

1. O(1) - 恒定時(shí)間

無(wú)論輸入大小如何，運(yùn)行時(shí)間都保持不變。這些操作是最有效率的。

示例：通過(guò)索引訪問(wèn)數(shù)組中的元素。

const numbers = [10, 20, 30, 40, 50];
console.log(numbers[2]); // Always takes the same time, no matter the array size

---

2. O(log n) - 對(duì)數(shù)時(shí)間

隨著輸入大小的增加，運(yùn)行時(shí)間呈對(duì)數(shù)增長(zhǎng)。這通常發(fā)生在二分搜索等分治算法中。

示例： 對(duì)排序數(shù)組進(jìn)行二分搜索。

function binarySearch(arr, target) {
    let start = 0;
    let end = arr.length - 1;

    while (start <= end) {
        const mid = Math.floor((start + end) / 2);

        if (arr[mid] === target) {
            return mid;
        } else if (arr[mid] < target) {
            start = mid + 1; // Search the right half
        } else {
            end = mid - 1; // Search the left half
        }
    }

    return -1; // Target not found
}

const arr = [1, 3, 5, 7, 9];
console.log(binarySearch(arr, 7)); // Output: 3

---

3. O(n) - 線性時(shí)間

運(yùn)行時(shí)間與輸入大小成比例增長(zhǎng)。當(dāng)您需要檢查每個(gè)元素一次時(shí)，就會(huì)發(fā)生這種情況。

示例：在未排序的數(shù)組中查找項(xiàng)目。

function linearSearch(arr, target) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) {
            return i; // Found
        }
    }
    return -1; // Not found
}

const items = [10, 20, 30, 40, 50];
console.log(linearSearch(items, 30)); // Output: 2

---

4. O(n2) - 二次時(shí)間

隨著輸入大小的增加，運(yùn)行時(shí)間呈二次方增長(zhǎng)。這在具有嵌套循環(huán)的算法中是典型的。

示例：基本的冒泡排序?qū)崿F(xiàn)。

const numbers = [10, 20, 30, 40, 50];
console.log(numbers[2]); // Always takes the same time, no matter the array size

---

5. O(2?) - 指數(shù)時(shí)間

每增加一個(gè)輸入，運(yùn)行時(shí)間就會(huì)加倍。這種情況發(fā)生在遞歸解決問(wèn)題的算法中，考慮所有可能的解決方案。

示例：遞歸計(jì)算斐波那契數(shù)。

function binarySearch(arr, target) {
    let start = 0;
    let end = arr.length - 1;

    while (start <= end) {
        const mid = Math.floor((start + end) / 2);

        if (arr[mid] === target) {
            return mid;
        } else if (arr[mid] < target) {
            start = mid + 1; // Search the right half
        } else {
            end = mid - 1; // Search the left half
        }
    }

    return -1; // Target not found
}

const arr = [1, 3, 5, 7, 9];
console.log(binarySearch(arr, 7)); // Output: 3

---

可視化大O

以下是隨著輸入大小的增加，不同 Big O 復(fù)雜度的比較：

---

增長(zhǎng)率說(shuō)明

想象一下您正在解決一個(gè)問(wèn)題，并且輸入大小增加。以下是不同復(fù)雜度的算法如何隨著輸入大小的增加而擴(kuò)展：

• O(1) 無(wú)論輸入如何，都保持不變。
• O(log n) 增長(zhǎng)緩慢，非常適合大輸入。
• O(n) 與輸入大小成比例增長(zhǎng)。
• O(n2) 及更高的值對(duì)于大輸入很快變得不切實(shí)際。

---

用代碼可視化 Big O

以下是如何使用簡(jiǎn)單的計(jì)數(shù)器可視化不同復(fù)雜度的操作數(shù)量：

const numbers = [10, 20, 30, 40, 50];
console.log(numbers[2]); // Always takes the same time, no matter the array size

---

關(guān)于 Big O 的常見(jiàn)誤解

1. Big O ≠ 實(shí)際表現(xiàn)：Big O 告訴您表現(xiàn)如何衡量，而不是所花費(fèi)的確切時(shí)間。
   • 例如，對(duì)于小輸入大小，具有較小常數(shù)因子的 O(n) 算法可能優(yōu)于 O(log n) 算法。
2. 最佳情況與最壞情況：Big O 通常描述最壞的情況。例如，搜索不在列表中的項(xiàng)目。
3. 并非所有嵌套循環(huán)都是 O(n2)：復(fù)雜性取決于內(nèi)循環(huán)處理的元素?cái)?shù)量。

---

初學(xué)者實(shí)用技巧

1. 關(guān)注 O(1)、O(n) 和 O(n2)：這些是您會(huì)遇到的最常見(jiàn)的復(fù)雜性。
2. 衡量性能：使用 Chrome DevTools 等工具對(duì)您的代碼進(jìn)行基準(zhǔn)測(cè)試。
3. 重構(gòu)以提高效率：代碼運(yùn)行后，識(shí)別復(fù)雜性較高的部分并進(jìn)行優(yōu)化。
4. 不斷學(xué)習(xí)：LeetCode 和 HackerRank 等平臺(tái)為理解 Big O 提供了很好的練習(xí)。

---

結(jié)論

大 O 表示法是評(píng)估算法效率和了解代碼擴(kuò)展方式的重要工具。通過(guò)掌握基礎(chǔ)知識(shí)并分析常見(jiàn)模式，您將能夠很好地編寫(xiě)高性能的 JavaScript 應(yīng)用程序。

編碼愉快！ ？

以上是理解 JavaScript 中的大 O 表示法和時(shí)間復(fù)雜度的詳細(xì)內(nèi)容。更多信息請(qǐng)關(guān)注PHP中文網(wǎng)其他相關(guān)文章！