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

為什么使用大 O 表示法？

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

示例：求和

讓我們探索兩種計算從 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;
}

分析復(fù)雜性

在選項 1 中，如果 n 為 100，則循環(huán)運(yùn)行 100 次。相反，選項 2 始終執(zhí)行固定數(shù)量的運(yùn)算（乘法、加法和除法）。因此：

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

免責(zé)聲明

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

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

什么是大 O 表示法？

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

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

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)，因此當(dāng) nnn 增加時，操作數(shù)量呈二次方增加。對于 n= 2，有 4 次操作，對于 n=3，有 9 次操作，導(dǎo)致 O(n^2)。

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

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

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

簡化分析

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

• 算術(shù)運(yùn)算被視為常數(shù)時間。
• 變量賦值是常數(shù)時間。
• 訪問數(shù)組（通過索引）或?qū)ο螅ㄍㄟ^鍵）中的元素是常數(shù)時間。
• 對于循環(huán)，復(fù)雜度是循環(huán)的長度乘以循環(huán)內(nèi)部發(fā)生的事情的復(fù)雜度。

空間復(fù)雜度

雖然我們關(guān)注時間復(fù)雜度，但也可以使用 Big O 來計算空間（內(nèi)存）復(fù)雜度。有些人在計算中包含輸入大小，但僅關(guān)注算法所需的空間通常更有用本身。

空間復(fù)雜度規(guī)則（基于 JavaScript）：

• 大多數(shù)原始值（布爾值、數(shù)字等）都是常量空間。
• 字符串需要 O(n) 空間（其中 n 是字符串長度）。
• 引用類型（數(shù)組、對象）一般都是 O(n)，其中 n 是數(shù)組的長度或?qū)ο笾墟I的數(shù)量。

示例

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

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

對于創(chuàng)建新數(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!");
}

這里，空間復(fù)雜度是 O(n)，因為我們?yōu)橐粋€新數(shù)組分配空間，該數(shù)組隨著輸入數(shù)組的大小而增長。

結(jié)論

Big O Notation 提供了一個框架，用于以獨(dú)立于硬件和具體實(shí)現(xiàn)細(xì)節(jié)的方式分析算法的效率。理解這些概念對于開發(fā)高效的代碼至關(guān)重要，尤其是隨著數(shù)據(jù)規(guī)模的增長。通過關(guān)注性能擴(kuò)展方式，開發(fā)人員可以就在其應(yīng)用程序中使用哪些算法做出明智的選擇。

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