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

本文將透過 JavaScript 中適合初學(xué)者的範(fàn)例來探索 Big O 表示法和常見時間複雜度的基礎(chǔ)知識

什麼是大 O 表示法？

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

1. 時間複雜度：演算法的執(zhí)行時間如何隨輸入大小的變化而改變。
2. 空間複雜度：演算法的記憶體使用量如何隨輸入大小的變化而變化。

目標(biāo)是評估演算法隨著輸入大小的增長而表現(xiàn)如何，並專注於最壞的情況。

---

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

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

• 一種方法是翻閱每一頁，直到找到名稱（線性搜尋）。
• 另一種是從中間開始，有系統(tǒng)地縮小範(fàn)圍（二分查找）。

兩種方法都可以解決問題，但是隨著電話簿大小的增長，它們的效率差異很大。 Big O 幫助我們比較這些方法並選擇最好的方法。

---

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

以下是常見的 Big O 複雜性，並透過 JavaScript 中的實際範(fàn)例進行了解釋。

---

1. O(1) - 恆定時間

無論輸入大小為何，運轉(zhuǎn)時間都保持不變。這些操作是最有效率的。

範(fàn)例：透過索引存取陣列中的元素。

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) - 對數(shù)時間

隨著輸入大小的增加，運行時間呈對數(shù)增長。這通常發(fā)生在二分搜尋等分治演算法中。

範(fàn)例： 對排序數(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

---

3. O(n) - 線性時間

運行時間與輸入大小成比例增長。當(dāng)您需要檢查每個元素一次時，就會發(fā)生這種情況。

範(fàn)例：在未排序的陣列中尋找項目。

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) - 二次時間

隨著輸入大小的增加，運行時間呈現(xiàn)二次方成長。這在具有嵌套循環(huán)的演算法中是典型的。

範(fàn)例：基本的冒泡排序?qū)嵶鳌?

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ù)時間

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

範(fàn)例：遞歸計算斐波那契數(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 複雜度的比較：

---

成長率說明

想像一下您正在解決一個問題，並且輸入大小增加。以下是不同複雜度的演算法如何隨著輸入大小的增加而擴展：

• O(1) 無論輸入如何，都保持不變。
• O(log n) 成長緩慢，非常適合大輸入。
• O(n) 與輸入大小成比例成長。
• O(n2) 及更高的值對於大輸入很快變得不切實際。

---

用代碼可視化 Big O

以下是如何使用簡單的計數(shù)器來視覺化不同複雜度的操作數(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 的常見誤解

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

---

初學(xué)者實用技巧

1. 專注於 O(1)、O(n) 和 O(n2)：這些是您會遇到的最常見的複雜性。
2. 衡量效能：使用 Chrome DevTools 等工具對您的程式碼進行基準(zhǔn)測試。
3. 重構(gòu)以提高效率：程式碼運行後，識別複雜性較高的部分並進行最佳化。
4. 不斷學(xué)習(xí)：LeetCode 和 HackerRank 等平臺為理解 Big O 提供了很好的練習(xí)。

---

結(jié)論

大 O 表示法是評估演算法效率和了解程式碼擴充方式的重要工具。透過掌握基礎(chǔ)知識並分析常見模式，您將能夠很好地編寫高效能的 JavaScript 應(yīng)用程式。

編碼愉快！ ？

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