什么是大O符號

本篇內容介紹了“什么是大O符號”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！

時間復雜度vs空間復雜度

大O符號用于度量時間復雜度和空間復雜度。

• 時間復雜度：為完成整體操作而必須執行的小操作的數量。

• 空間復雜度：運行算法中的代碼所需的額外內存量——通常被稱為輔助空間復雜度，也就是說它僅指代算法所占用的空間，不包括輸入所占用的空間。

復雜度類型

時間復雜度可以分為幾種不同的類型。下列是幾種較常見類型：

• 常數階/O(1)：無論數據集多大，始終在相同的時間或空間中執行。

• 對數階/O(log n)：為獲得給定數據，固定數據所必須增加的冪。

• 線性階/ O(n)：復雜度與輸入數據的大小直接相關。

• 線性對數階/ O(nlog n)：對輸入中的每一項執行O(log n)操作。

• 平方階/O(n²)：性能與輸入數據的平方大小成正比。

圖源：Colt Steele的JavaScript算法和數據結構大師班

有助于確定時空復雜度的一般規則

這些規則是可以起作用的方向，但不保證每次都有效果。

確定時間復雜度：

• 算術運算恒定

• 變量賦值為常數

• 數組(通過索引)或對象(通過鍵)中的訪問元素是常量

• 在循環中，復雜度是循環的長度乘以循環內發生的任何事情的復雜度。

確定空間復雜度：

• 大多數基元是常量空間。(布爾常量，數字，未定義變量，空。)

• 字符串需要O(n)空間，其中n是字符串的長度。

• 引用類型通常為O(n)，其中n是對象的數組長度或鍵數。

來看一些例子

圖源：Colt Steele的JavaScript算法和數據結構大師班

至于空間復雜度，addUpToN有2個變量賦值(total和i)。當循環完成其操作時，這些變量會被重新分配，但無論輸入數據集的大小如何，這些變量占用的空間都保持不變。空間復雜度將為常數階/O(1)。

這里有3個簡單的運算(乘、加、除)。不管n的大小如何，操作的數量保持不變。addUpToNAgain的時間復雜度為常數階/O(1)。

此時只會返回一個值。輸入值不會改變分配給此函數的空間。因此，空間復雜度也是線性階/O(1)。

在這里，有一個線性階O(n)運算嵌套在另一個O(n)運算中。當輸入的n值縮放時，運行時間隨之發生變動。sumEachPair的時間復雜度是平方階/O(n²)。

回顧一下前文所述的一般規則，這個案例正好對應了其中一條：引用類型一般是O(n)，其所需的空間量與輸入值直接相關。空間復雜度則為線性階/O(n)。

想分析算法的性能，可以使用大O符號幫助分析，大O符號可以加深對算法的時間和空間要求的理解。

總之，程序員要理解好所編寫的代碼的時空復雜度，進而確保運行時間和執行速度達到最快，同時保證代碼始終保持在其運行系統的實體存儲范圍內，“修煉”成一個高效的程序員。

“什么是大O符號”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！