什么是大O符號(hào)

本篇內(nèi)容介紹了“什么是大O符號(hào)”的有關(guān)知識(shí)，在實(shí)際案例的操作過程中，不少人都會(huì)遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

時(shí)間復(fù)雜度vs空間復(fù)雜度

大O符號(hào)用于度量時(shí)間復(fù)雜度和空間復(fù)雜度。

• 時(shí)間復(fù)雜度：為完成整體操作而必須執(zhí)行的小操作的數(shù)量。

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

復(fù)雜度類型

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

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

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

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

• 線性對(duì)數(shù)階/ O(nlog n)：對(duì)輸入中的每一項(xiàng)執(zhí)行O(log n)操作。

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

圖源：Colt Steele的JavaScript算法和數(shù)據(jù)結(jié)構(gòu)大師班

有助于確定時(shí)空復(fù)雜度的一般規(guī)則

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

確定時(shí)間復(fù)雜度：

• 算術(shù)運(yùn)算恒定

• 變量賦值為常數(shù)

• 數(shù)組(通過索引)或?qū)ο?通過鍵)中的訪問元素是常量

• 在循環(huán)中，復(fù)雜度是循環(huán)的長度乘以循環(huán)內(nèi)發(fā)生的任何事情的復(fù)雜度。

確定空間復(fù)雜度：

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

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

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

來看一些例子

圖源：Colt Steele的JavaScript算法和數(shù)據(jù)結(jié)構(gòu)大師班

至于空間復(fù)雜度，addUpToN有2個(gè)變量賦值(total和i)。當(dāng)循環(huán)完成其操作時(shí)，這些變量會(huì)被重新分配，但無論輸入數(shù)據(jù)集的大小如何，這些變量占用的空間都保持不變?？臻g復(fù)雜度將為常數(shù)階/O(1)。

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

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

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

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

想分析算法的性能，可以使用大O符號(hào)幫助分析，大O符號(hào)可以加深對(duì)算法的時(shí)間和空間要求的理解。

總之，程序員要理解好所編寫的代碼的時(shí)空復(fù)雜度，進(jìn)而確保運(yùn)行時(shí)間和執(zhí)行速度達(dá)到最快，同時(shí)保證代碼始終保持在其運(yùn)行系統(tǒng)的實(shí)體存儲(chǔ)范圍內(nèi)，“修煉”成一個(gè)高效的程序員。

“什么是大O符號(hào)”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！