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

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

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

例：求和

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

選項 1：使用循環(huán)

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，則循環(huán)運行 100 次。相反，選項 2 總是執(zhí)行固定數(shù)量的運算（乘法、加法和除法）。因此：

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

免責聲明

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

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

什麼是大 O 表示法？

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

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

O(n^2) 的範例

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

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

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

另一個例子：向上和向下計數(shù)

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

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

簡化分析

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

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

空間複雜度

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

空間複雜度規(guī)則（基於 JavaScript）：

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

範例

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

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

對於建立新數(shù)組的函數(shù)：

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)，因為我們?yōu)橐粋€新數(shù)組分配空間，該數(shù)組隨著輸入數(shù)組的大小而增長。

結(jié)論

Big O Notation 提供了一個框架，以獨立於硬體和具體實現(xiàn)細節(jié)的方式分析演算法的效率。理解這些概念對於開發(fā)高效的程式碼至關(guān)重要，尤其是隨著資料規(guī)模的成長。透過專注於效能擴展方式，開發(fā)人員可以就在其應(yīng)用程式中使用哪些演算法做出明智的選擇。

以上是大 O 表示法：簡單指南的詳細內(nèi)容。更多資訊請關(guān)注PHP中文網(wǎng)其他相關(guān)文章！