初學者大 O 表示法：實用指南

有沒有想過為什麼有些程式碼運作得很快，而其他程式碼卻在爬行？輸入大 O 表示法 - 開發人員用來討論演算法效率的秘密語言。讓我們簡單地分解一下。

什麼是大 O 表示法？

大 O 表示法描述了程式碼的效能如何隨著輸入大小的成長而擴展。將其視為衡量當您給代碼分配更多工作要做時需要多長時間。

常見的大O複雜性

O(1) - 恆定時間

性能的聖杯。無論您的輸入有多大，操作所需的時間都是相同的。

function getFirstElement(array) {
    return array[0];  // Always one operation
}

O(log n) - 對數時間

通常出現在每次將問題一分為二的演算法中。二分查找就是一個典型的例子。

function binarySearch(sortedArray, target) {
    let left = 0;
    let right = sortedArray.length - 1;

    while (left <= right) {
        let mid = Math.floor((left + right) / 2);

        if (sortedArray[mid] === target) return mid;
        if (sortedArray[mid] < target) left = mid + 1;
        else right = mid - 1;
    }

    return -1;
}

O(n) - 線性時間

效能隨輸入大小線性擴展。常見於需要查看每個元素一次的演算法。

function findMax(array) {
    let max = array[0];
    for (let i = 1; i < array.length; i++) {
        if (array[i] > max) max = array[i];
    }
    return max;
}

O(n log n) - 線性時間

常見於歸併排序和快速排序等高效排序演算法中。

function mergeSort(array) {
    if (array.length <= 1) return array;

    const mid = Math.floor(array.length / 2);
    const left = mergeSort(array.slice(0, mid));
    const right = mergeSort(array.slice(mid));

    return merge(left, right);
}

O(n²) - 二次時間

常見於巢狀循環中。隨著輸入大小的增加，效能會迅速下降。

function bubbleSort(array) {
    for (let i = 0; i < array.length; i++) {
        for (let j = 0; j < array.length - i - 1; j++) {
            if (array[j] > array[j + 1]) {
                [array[j], array[j + 1]] = [array[j + 1], array[j]];
            }
        }
    }
    return array;
}

編寫高效程式碼的實用技巧

1. 盡量避免巢狀循環

   • 使用雜湊表進行查找而不是巢狀迭代
   • 先考慮是否可以透過排序來解決你的問題

2. 選擇適當的資料結構

   • 可快速存取的有序資料數組
   • 用於快速尋找的雜湊表
   • 用於維護排序資料的二元樹

3. 空間與時間的權衡

   • 有時使用更多記憶體可以顯著提高時間複雜度
   • 快取經常存取的值

常見陷阱

1. 隱藏循環

// Looks like O(n), actually O(n²)
array.forEach(item => {
    const index = anotherArray.indexOf(item);  // indexOf is O(n)
});

1. 循環中的字串連接

// Poor performance
let result = '';
for (let i = 0; i < n; i++) {
    result += someString;  // Creates new string each time
}

// Better approach
const parts = [];
for (let i = 0; i < n; i++) {
    parts.push(someString);
}
const result = parts.join('');

實際應用

了解 Big O 可以幫助您：

• 選擇正確的演算法和資料結構
• 最佳化效能瓶頸
• 做出更好的架構決策
• 通過技術面試

其他資源

• 演算法導論 - 綜合學術資源
• Big O Cheat Sheet - 常用操作快速參考
• Visualgo - 視覺化演算法與資料結構

結論

大 O 表示法看起來很學術，但它是編寫更好程式碼的實用工具。從這些基礎知識開始，您將開始編寫更有效率的演算法。

---

您在演算法最佳化方面有什麼經驗？在下面的評論中分享您的想法和問題！

以上是初學者大 O 表示法：實用指南的詳細內容。更多資訊請關注PHP中文網其他相關文章！