大 O 表示法：簡單指南-js教程-PHP中文網

Big O Notation: A Simple Guide

大 O 表示法是一個數學概念，用於描述演算法隨著輸入大小的增長而在時間和空間方面的性能或複雜性。它幫助我們了解演算法的運行時間如何隨著輸入的增加而增加，從而可以對不同演算法進行更標準化的比較。

為什麼要使用大 O 表示法？

在比較演算法時，僅依賴執行時間可能會產生誤導。例如，一種演算法可能會在一小時內處理大量資料集，而另一種演算法可能需要四個小時。但是，執行時間可能會根據電腦和其他正在運行的進程而有所不同。相反，我們使用 Big O 表示法來關注執行的操作數量，這提供了更一致的效率衡量標準。

例：求和

讓我們來探索兩種計算從 1 到 n 的所有數字總和的方法：

選項 1：使用循環

function addUpTo(n) {
    let total = 0;
    for (let i = 1; i <= n; i++) {
        total += i;
    }
    return total;
}

登入後複製

選項 2：使用公式

function addUpTo(n) {
    return n * (n + 1) / 2;
}

登入後複製

分析複雜性

在選項 1 中，如果 n 為 100，則循環運行 100 次。相反，選項 2 總是執行固定數量的運算（乘法、加法和除法）。因此：

選項1是O(n)：時間複雜度隨n線性成長。
選項 2 為 O(1)：無論輸入大小為何，時間複雜度保持不變。

免責聲明

雖然選項2涉及三種運算（乘法、加法、除法），但我們關注的是Big O分析的整體趨勢。因此，我們不是將其表示為 O(3n)，而是將其簡化為 O(n)。同樣，O(n 10) 簡化為 O(n)，O(n^2 5n 8) 簡化為 O(n^2)。在大 O 表示法中，我們考慮最壞的情況，其中最高階項對表現的影響最大。

除了上面列出的常見複雜度之外，還有其他形式的表示法，例如表示為 O(log n) 的對數時間複雜度。

什麼是大 O 表示法？

大 O 表示法允許我們根據輸入大小來形式化演算法運行時間的成長。我們不關注特定的操作計數，而是將演算法分為更廣泛的類別，包括：

恆定時間：O(1) - 演算法的效能不隨輸入大小而變化。
線性時間：O(n) - 效能隨著輸入大小線性增長。
二次方時間：O(n^2) - 隨著輸入大小的增加，效能呈現二次方成長。

O(n^2) 的範例

考慮以下函數，它印出從 0 到 n 的所有數字對：

function addUpTo(n) {
    let total = 0;
    for (let i = 1; i <= n; i++) {
        total += i;
    }
    return total;
}

登入後複製

在這種情況下，函數有兩個巢狀循環，因此當 nnn 增加時，操作數量呈現二次方增加。對於 n= 2，有 4 次操作，對於 n=3，有 9 次操作，導致 O(n^2)。

另一個例子：向上和向下計數

function addUpTo(n) {
    return n * (n + 1) / 2;
}

登入後複製

乍一看，人們可能會認為這是 O(n^2)，因為它包含兩個循環。然而，兩個循環獨立運行並隨 n 線性縮放。因此，總體時間複雜度為 O(n)。

簡化分析

分析程式碼複雜性的各個方面可能很複雜，但一些通用規則可以簡化事情：

算術運算被視為常數時間。
變數賦值是常數時間。
存取數組（透過索引）或物件（透過鍵）中的元素是常數時間。
對於循環，複雜度是循環的長度乘以循環內部發生的事情的複雜度。

空間複雜度

雖然我們專注於時間複雜度，但也可以使用 Big O 來計算空間（記憶體）複雜度。有些人在計算中包含輸入大小，但僅關注演算法所需的空間通常更有用本身。

空間複雜度規則（基於 JavaScript）：

大多數原始值（布林值、數字等）都是常數空間。
字串需要 O(n) 空間（其中 n 是字串長度）。
引用型別（陣列、物件）一般都是 O(n)，其中 n 是陣列的長度或物件中鍵的數量。

範例

function printAllPairs(n) {
    for (var i = 0; i < n; i++) {
        for (var j = 0; j < n; j++) {
            console.log(i, j);
        }
    }
}

登入後複製

在此函數中，空間複雜度為 O(1)，因為無論輸入大小如何，我們都使用恆定量的空間（兩個變數）。

對於建立新數組的函數：

function countUpAndDown(n) {
    console.log("Going up!");
    for (var i = 0; i < n; i++) {
        console.log(i);
    }
    console.log("At the top!\nGoing down...");
    for (var j = n - 1; j >= 0; j--) {
        console.log(j);
    }
    console.log("Back down. Bye!");
}

登入後複製

這裡，空間複雜度是 O(n)，因為我們為一個新數組分配空間，該數組隨著輸入數組的大小而增長。