本文轉(zhuǎn)載自公眾號(hào)“讀芯術(shù)”(ID：AI_Discovery)。

首先，什么是代碼效率?這個(gè)熱門術(shù)語在各種會(huì)議、講座和博客中已經(jīng)被用濫了。它被廣泛用于描述代碼的速度和可靠性，與軟件的算法效率和運(yùn)行時(shí)執(zhí)行速度密切相關(guān)。在當(dāng)下，這個(gè)人工智能、可擴(kuò)展性和機(jī)器學(xué)習(xí)處于軟件開發(fā)前沿的時(shí)代，這個(gè)話題始終被反復(fù)提及。

[[344944]]

那么什么是大O符號(hào)呢?在計(jì)算機(jī)科學(xué)領(lǐng)域中，它是用來描述算法的性能和效率以及分析整體性能的工具，被用于確定完成算法執(zhí)行所需時(shí)間或空間的最壞情況。大O符號(hào)是基于性能來確定函數(shù)最佳實(shí)現(xiàn)的寶貴工具，它提供了一種正式的說法，用于討論算法的運(yùn)行時(shí)間如何根據(jù)輸入而變化。

時(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)的長(zhǎng)度乘以循環(huán)內(nèi)發(fā)生的任何事情的復(fù)雜度。

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

• 大多數(shù)基元是常量空間。(布爾常量，數(shù)字，未定義變量，空。)
• 字符串需要O(n)空間，其中n是字符串的長(zhǎng)度。
• 引用類型通常為O(n)，其中n是對(duì)象的數(shù)組長(zhǎng)度或鍵數(shù)。

來看一些例子

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

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

這里有3個(gè)簡(jiǎn)單的運(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è)高效的程序員。