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

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

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

例：求和

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

選項 1：使用循環

function addUpTo(n) {
    let total = 0;
    for (let i = 1; i 




  
  
  選項 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 printAllPairs(n) {
    for (var i = 0; i 



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


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




function countUpAndDown(n) {
    console.log("Going up!");
    for (var i = 0; i = 0; j--) {
        console.log(j);
    }
    console.log("Back down. Bye!");
}





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


  
  
  簡化分析


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

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

空間複雜度

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

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

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

範例

function sum(arr) {
    let total = 0;
    for (let i = ; i 



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

對於建立新數組的函數：



function double(arr) {
    let newArr = [];
    for (let i = 0; i 



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


  
  
  結論


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