想像一下我們有不同的方式來寫相同的程式碼。我們如何判斷哪一個是最好的？這就是 Big O 表示法的用武之地。它可以幫助我們衡量程式碼需要多少時間和空間，從而更容易比較它們。
Big O，也稱為“順序”，是描述演算法在最壞情況下運行所需時間的一種方式。它讓我們了解演算法根據輸入大小所需的最大時間。我們將其寫為 O(f(n))，其中 f(n) 表示演算法解決輸入大小為 n 的問題需要多少步驟。
讓我們試著透過範例來理解「寫一個接受字串輸入並傳回反向副本的函數」
好吧，我正在與您分享一個 Stack Overflow 解決方案，以及上圖，如您所見。它展示了解決相同問題的 10 種不同方法，每種方法都有獨特的方法。
現在的問題是：我們如何知道哪一個是最好的？
我們的目標是理解時間和空間複雜性。為此，讓我們探索一個包含兩個不同程式碼片段的具體範例，以便我們可以清楚地了解這些概念的重要性。
這是一個名為 addUpTo 的函數。函數使用 for 循環，運行直到達到 n 的長度並傳回總和。
現在，讓我們來看另一個實現相同功能的範例：
現在，在這種情況下「更好」到底代表什麼？
更快嗎？
它使用的記憶體較少嗎？
可讀性更好嗎？
通常，人們在考慮可讀性之前會專注於前兩個因素——速度和記憶體使用情況。在這種情況下，我們將重點放在前兩者。為了測量兩個程式碼範例的效能，我們將使用 JavaScript 的內建計時函數來分析和比較它們的執行時間。
在上面的程式碼中，我加入了 t1 和 t2，它們利用了 JavaScript 中內建的 Performance.now() 函數。這個函數幫助我們測量程式碼執行所花費的時間，使我們能夠準確地比較兩種方法的效能。
確實，執行時間根據不同因素而有所不同，你在我的電腦上也可以看到——時間不一致。 Performance.now() 函數沒有給我們一個固定的時間，但它提供了一個有用的比較估計。
現在，讓我們來看第二個例子：
現在，觀察第一個和第二個程式碼範例之間執行時間的差異。第二個明顯比第一個快。
但是僅僅依賴時間測量有什麼問題呢？
不同機器記錄的時間不同。
即使是同一台機器，每次運作也會記錄不同的時間。
對於非常快速的演算法，速度測量可能不夠精確，無法進行準確的比較。
這些因素使得基於時間的效能評估不可靠，尤其是對於快速演算法。
好吧，如果沒時間那怎麼辦？
這就是 Big O 將幫助我們衡量時間複雜度和空間複雜度的地方。所以大O表示法是一種形式化模糊計數的方法。它使我們能夠正式討論演算法的運行時間如何隨著輸入的增長而增長。
如果隨著 n 的增加，計算機必須執行的簡單操作的數量最終小於常數乘以 f(n)，則我們稱演算法為 O(f(n))。
f(n) 可以是線性的 (f(n) = n)
f(n) 可以是二次方 (f(n) = n2)
f(n) 可以是常數 (f(n) = 1)
f(n) 可能完全不同！
這是一個例子：
在這種情況下，我們只有 3 個操作，無論輸入的大小，它總是保持 3 個操作。這就是為什麼我們可以說這個函數的時間複雜度是常數，或是O(1).
現在這是第一個範例：
在這種情況下，隨著輸入 n 的增長，操作數量也會成比例增加。因此，時間複雜度取決於輸入的大小，使其O(n).
現在，讓我們來看另一個例子：
在此範例中，我們有兩個巢狀的 for 循環，都依賴 n（輸入）。這意味著隨著輸入n的成長，操作數量顯著增加。因此，這段程式碼的時間複雜度為 O(n²)，也稱為二次時間複雜度。
現在，讓我們來簡化大O表示法。在決定演算法的時間複雜度時，需要記住一些有用的經驗規則。這些指南源自 Big O 表示法的正式定義，使分析演算法變得更加容易。
O(2n) = O(n)
O(500) = O(1)
O(13n²) = O(n²)
O(n 10) = O(n)
O(1000n 500) = O(n)
O(n² 5n 8) = O(n²)
算術運算是常數
變數賦值是常數
存取陣列（按索引）或物件（按鍵）中的元素是常數
在循環中，複雜度是循環的長度乘以循環內發生的任何事情的複雜度
這是大 O 圖表：
到目前為止，從範例中，我們已經了解了O(n)（線性時間複雜度）、O(1)（恆定時間複雜度）和O(n²)（二次時間複雜度）。這些涵蓋了操作隨輸入大小而增長的基本模式。
稍後我們將討論 O(log n) 和 O(n log n)——對數和線性時間複雜度。
到目前為止，我們一直在關注時間複雜度：隨著輸入大小的增加，我們如何分析演算法的運行時間？
我們也可以使用大 O 表示法來分析空間複雜度：我們需要分配多少額外記憶體才能運行演算法中的程式碼？
輸入怎麼樣？
有時您會聽到術語“輔助空間複雜度”，指的是演算法所需的空間，不包括輸入佔用的空間。除非另有說明，當我們談論空間複雜度時，從技術上講，我們將談論輔助空間複雜度。
JS 中的空間複雜度
大多數基元（布林值、數字、未定義、null）都是常數空間
字串需要 O(n) 空間（其中 n 是字串長度） 引用類型通常是 O(n)，其中 n 是長度（對於數組）或鍵的數量（對於物件）
記住，我們談論的是空間複雜度，而不是時間複雜度。在這段程式碼中，我們可以看到只有兩個變數。無論輸入增長多大，這兩個變數將始終存在於程式碼中。由於隨著輸入的增加，我們沒有添加任何新變量，因此我們可以說空間複雜度為 O(1)，這意味著它是恆定的空間複雜度。
讓我們用另一個例子來理解：
在此程式碼中，函數在將輸入數組中的每個元素加倍後傳回 newArr。由於newArr的大小與輸入arr的大小成正比，因此newArr所使用的空間會隨著輸入大小的增加而成長。與前面的範例不同，其中空間是恆定的，這裡的空間複雜度取決於輸入陣列的大小。因此，空間複雜度為O(n)，表示它是線性的。
我希望這能讓空間複雜度更加清晰——就像時間複雜度一樣，我們使用 Big O 表示法來測量它。到目前為止，您已經了解了不同的時間複雜度，按複雜度遞增的順序：O(1)、O(log n)、O(n )、O(n log n)、O(n²)、O(n3) 等等。然而，我們還沒有探索對數時間複雜度。
接下來，我們將深入研究對數時間複雜度並看看它是如何運作的。
我們遇到了一些最常見的複雜性：O(1)、O(n)、O(n2)。有時大 O 表達式涉及更複雜的數學表達式。對數出現得比你想像的更頻繁！
日誌又是什麼？
log2 (8) = 3 → 2³ = 8
log2（值）= 指數 → 2^指數 = 值
我們將省略 2，這表示：
log === log2
數字的對數大致衡量在該數字小於或等於 1 之前您可以將該數字除以 2 的次數。這使得對數時間複雜度非常有效率。正如您在圖表中看到的，O(1)（恆定時間）非常接近 O(log n)，這太棒了！另外值得注意的是，O(n log n) 在效率方面比 O(n²) 好得多，使其成為許多演算法的首選複雜度。
某些搜尋演算法具有對數時間複雜度。
高效的排序演算法涉及對數。
遞歸有時涉及對數空間複雜度。
太棒了！我們已經涵蓋了空間和時間複雜度的大部分關鍵點。請記住，掌握這些概念需要練習，因此如果不能立即完全清楚，請不要感到不知所措。慢慢來，多次查看材料，並根據需要重新查看範例。通常需要重複幾次才能真正理解這些想法，所以對自己要有耐心！
最後，讓我們再回顧一下：
為了分析演算法的效能，我們使用大 O 表示法
大 O 表示法可以讓我們對演算法的時間或空間複雜度有一個高層次的理解
大 O 表示法不關心精確度，只關心整體趨勢（線性？二次？常數？）
再說一遍，大 O 表示法無所不在，所以要多加練習！
我們CreoWis相信公開分享知識可以幫助開發者社群成長。讓我們充滿熱情地協作、構思和打造，為世界提供令人驚嘆的產品體驗。
讓我們聯絡：
X/Twitter
領英
網址
本文由 CreoWis 的一位充滿熱情的開發人員 Syket Bhattachergee 撰寫。您可以透過 X/Twitter、LinkedIn、 聯絡他，並在 GitHub 上關注他的工作。
以上是理解大 O 表示法：時間和空間複雜性初學者指南的詳細內容。更多資訊請關注PHP中文網其他相關文章！
