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

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

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

例：求和

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

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

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

選項(xiàng) 2：使用公式

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

分析複雜性

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

• 選項(xiàng)1是O(n)：時(shí)間複雜度隨n線性成長(zhǎng)。
• 選項(xiàng) 2 為 O(1)：無(wú)論輸入大小為何，時(shí)間複雜度保持不變。

免責(zé)聲明

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

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

什麼是大 O 表示法？

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

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

O(n^2) 的範(fàn)例

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

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

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

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

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

乍一看，人們可能會(huì)認(rèn)為這是 O(n^2)，因?yàn)樗瑑蓚€(gè)循環(huán)。然而，兩個(gè)循環(huán)獨(dú)立運(yùn)行並隨 n 線性縮放。因此，總體時(shí)間複雜度為 O(n)。

簡(jiǎn)化分析

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

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

空間複雜度

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

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

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

範(fàn)例

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

在此函數(shù)中，空間複雜度為 O(1)，因?yàn)闊o(wú)論輸入大小如何，我們都使用恆定量的空間（兩個(gè)變數(shù)）。

對(duì)於建立新數(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àn)槲覀優(yōu)橐粋€(gè)新數(shù)組分配空間，該數(shù)組隨著輸入數(shù)組的大小而增長(zhǎng)。

結(jié)論

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

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