什麼是big-o符號？

你的程式碼需要有效率，但是你如何證明某個東西有多高效呢？與大O！...

你有沒有想過為什麼你寫的程式要花這麼長時間才能執行？也許您想知道是否可以提高程式碼的效率。瞭解程式碼執行如何將程式碼提升到下一個級別。Big-O表示法是計算程式碼實際效率的一個方便工具。

什麼是大o符號(big-o notation)？

Big-O表示法提供了一種計算執行程式碼所需時間的方法。您可以實際計算程式碼執行所需的時間，但是使用這種方法，很難捕捉到小的時間差異。例如，執行20到50行程式碼所需的時間非常少。然而，在一個大型專案中，這些低效率可能會累積起來。

Big-O表示法計算一個演算法必須執行多少步才能衡量其效率。如果需要調整程式碼以提高效率，那麼以這種方式處理程式碼是非常有效的。Big-O表示法將使您能夠根據執行所需的步驟數來度量不同的演算法，並客觀地比較演算法的效率。

如何計算big-o符號

讓我們考慮兩個函式來計算一個抽屜中有多少隻襪子。每個函式獲取襪子對的數量並返回單個襪子的數量。程式碼是用Python編寫的，但這並不影響我們計算步驟數的方式。

演算法1：

def sockCounter(numberOfPairs): individualSocks = 0 for x in range(numberOfPairs): individualSocks = individualSocks + 2 return individualSocks

演算法2：

def sockCounter(numberOfPairs): return numberOfPairs * 2

這是一個愚蠢的例子，你應該能夠很容易地判斷哪種演算法更有效。但是為了練習，讓我們把每一個都講一遍。

相關：什麼是程式設計中的函式？

演算法1有很多步驟：

它為變數individualSocks賦值為零。
它給變數i賦值為1。
它將i的值與numberOfPairs進行比較。
它增加了兩個單獨的襪子。
它將個人襪子的增值分配給自己。
它使i增加1。
然後，它在步驟3到6之間迴圈，迴圈次數與（individualsocks-1）相同。

對於演算法1，我們必須完成的步驟數可以表示為：

4n + 2

有四個步驟，我們必須完成n次。在這種情況下，n等於numberOfPairs的值。還有兩個步驟一次完成。

相比之下，演算法2只有一個步驟。numberOfPairs的值乘以2。我們可以這樣說：

如果還不明顯的話，我們現在可以很容易地看到演算法2的效率提高了很多。

大o分析

通常，當您對演算法的Big-O表示法感興趣時，您對整體效率更感興趣，而對步長的細粒度分析則不太感興趣。為了簡化表示法，我們可以只說明效率的大小。

在上述示例中，演算法2將表示為：

O(1)

但演算法1將簡化為：

O(n)

這個快速快照告訴我們演算法一的效率是如何與n的值聯絡在一起的。數量越大，演算法需要完成的步驟就越多。

線性碼

因為我們不知道n的值，所以考慮n的值如何影響需要執行的程式碼量更有幫助。在演算法1中，我們可以說這種關係是線性的。如果你畫出步數和n的值，你會得到一條上升的直線。

二次碼

並不是所有的關係都像線性例子那麼簡單。假設您有一個二維陣列，並且希望在陣列中搜索一個值。您可以建立如下演算法：

def searchForValue(targetValue, arraySearched): foundTarget = False for x in arraySearched: for y in x: if(y == targetValue): foundTarget = True return foundTarget

在本例中，步驟的數量取決於ArraySearchd中的陣列數量和每個陣列中的值數。因此，簡化的步驟數將為n*n或n²。

這個關係是一個二次關係，這意味著我們演算法中的步數隨著n呈指數增長。用Big-O表示法，你可以這樣寫：

O(n²)

相關：用於檢查、清理和最佳化CSS檔案的有用工具

對數碼

雖然還有很多其他的關係，但我們最後要討論的是對數關係。要重新整理記憶體，一個數字的對數是達到給定基數的數字所需的指數值。例如：

log 2 (8) = 3

對數等於3，因為如果我們的基數是2，我們需要一個指數值3才能得到數字8。

所以，對數函式的關係和指數函式的關係是相反的。隨著n的增加，執行演算法所需的新步驟也會減少。

乍一看，這似乎違反直覺。一個演算法的步長怎麼會比n增長慢呢？二進位制搜尋就是一個很好的例子。讓我們考慮一個演算法來搜尋唯一值陣列中的數字。

我們將從一個從最小到最大的陣列開始搜尋。
接下來，我們將檢查陣列中間的值。
如果您的號碼較高，我們將在搜尋中排除較低的號碼，如果號碼較低，我們將排除較高的號碼。
現在，我們來看看剩餘數字的中間數字。
同樣，我們將根據目標值是高於還是低於中間值來排除一半的數字。
我們將繼續這個過程，直到我們找到我們的目標，或確定它不在名單上。

正如您所看到的，由於二進位制搜尋每次都會消除一半的可能值，隨著n變大，對檢查陣列次數的影響幾乎沒有影響。為了用Big-O表示法來表示這一點，我們要寫：

O(log(n))

big-o符號的重要性

Big-O nation為您提供了一種快速簡便的方法來傳達演算法的效率。這樣就更容易在不同的演算法之間做出決定。如果您使用的是庫中的演算法，並且不一定知道程式碼的樣子，那麼這將非常有用。

當你第一次學習編碼時，你從線性函式開始。從上面的圖表中可以看出，這會讓你走得更遠。但是當你變得更有經驗並且開始構建更復雜的程式碼時，效率開始成為一個問題。瞭解如何量化程式碼的效率將為您提供所需的工具，以開始調整程式碼的效率並權衡演算法的優缺點。

發表於 2021-03-28 21:51
閱讀 ( 36 )
分類：程式設計

你可能感興趣的文章

路易斯點符號(lewis dot symbol)和劉易斯結構(lewis structure)的區別

...示化學鍵。目錄 1. 概述和主要區別 2. 劉易斯圓點符號是什麼 3. 劉易斯結構是什麼 4. 並排比較-劉易斯點符號和劉易斯結構的表格形式 5. 摘要什麼是路易斯點符號(lewis dot symbol)？一個點代表一個電子符號。因此，如果我們需要...

發佈於 2020-10-13 17:57
閲讀 ( 63 )

點群(point group)和空間組(space group)的區別

...格組合而成的空間群有230個。目錄 1.概述和主要區別 2. 什麼是點群 3. 什麼是太空小組 4. 並列比較-表格形式的點組與空間組 5. 摘要什麼是點群(point group)？晶體學點群是一組對稱操作，至少有一個點保持不變。點群中描述的...

發佈於 2020-10-14 09:33
閲讀 ( 134 )

化學符號(chemical symbol)和化學式(chemical formula)的區別

...，以及這些元素之間的比率。目錄 1. 概述和主要區別 2. 什麼是化學符號 3. 什麼是化學式 4. 並列比較-化學符號與化學式的表格形式 5. 摘要什麼是化學符號(chemical symbol)？化學符號是識別某種化學元素的程式碼。每個不同的化...

發佈於 2020-10-18 07:01
閲讀 ( 58 )

自上而下(top down)和自下而上分析(bottom up parsing)的區別

...編譯器中，它執行解析任務。目錄 1. 概述和主要區別 2. 什麼是自頂向下的解析 3. 什麼是自下而上的解析 4. 並排比較-表格形式的自頂向下與自下而上分析 5. 摘要什麼是自頂向下分析(top down parsing)？每種程式語言都有一組表...

發佈於 2020-10-18 09:45
閲讀 ( 53 )

鎳(nickel)和銀(silver)的區別

...素都在元素週期表的d塊中。目錄 1. 概述和主要區別 2. 什麼是鎳 3. 什麼是銀 4. 並列比較-鎳和銀的表格形式 5. 摘要什麼是鎳(nickel)？它是一種化學元素，原子序數為28，化學符號為Ni。它和銀很相似，因為它們都有光澤的金屬...

發佈於 2020-10-18 16:49
閲讀 ( 50 )

符號(symfony)和拉威爾(laravel)的區別

...，並使應用程式更加安全。目錄 1. 概述和主要區別 2. 什麼是Symfony 3. 什麼是拉威爾 4. Symfony和Laravel的相似之處 5. 並列比較——Symfony與Laravel的表格形式 6. 摘要什麼是符號(symfony)？ Symfony是一個流行的PHP web框架。它是一個開源...

發佈於 2020-10-18 18:43
閲讀 ( 38 )