算法的複雜性理論

我們如何衡量算法的速度

複雜度理論是對算法運行所需時間量（取決於輸入大小）的研究。 這對於軟件開發人員理解非常有用，因此他們可以高效地編寫代碼。 有兩種類型的複雜性：

空間複雜度：一個算法需要運行多少內存時間複雜度：一個算法需要運行多少時間。

通常我們比時間複雜度更擔心時間複雜度，因為我們可以重用算法需要運行的內存，但是我們不能重用運行時間。 買內存比買時間要容易。 如果您需要更多內存-您可以從Amazon，Google或Microsoft等提供商那裡租用服務器空間。 您也可以購買更多計算機以增加內存，而無需佔用服務器空間。 本文的其餘部分將介紹如何優化時間複雜度。

我們如何衡量時間複雜度？

新計算機通常會比舊計算機快，而臺式機通常會比智能手機快-那麼我們如何才能真正知道算法所需的絕對時間呢？

為了測量絕對時間，我們考慮算法執行的操作數。 任何算法的構造塊都是if語句和循環。 他們回答以下問題：（1）我們什麼時候應該進行手術？ （2）我們應該做幾次？ 我們希望使用盡可能少的if語句和循環來編寫代碼，以在任何計算機上實現最高效率。

為了分析算法，我們考慮輸入大小n-輸入項的數量。 我們想對算法的運行時間與輸入大小n有何關係做出很好的猜測。 這是增長的順序：給定輸入大小n時，算法將如何縮放和運行。

1. Input 10 items -> 10 ms

2. Input 100 items -> 100 ms (Good, linear growth)

3. Input 1,000 items -> 10,000 ms (Bad, exponential growth)

在上面的示例中，當我們輸入10個項目時，需要10毫秒來運行。 當我們輸入100個項目時，它需要100毫秒-這很好，因為我們輸入的增長與運行時間成比例地增加。

但是，下一步，我們輸入了1,000個項目，這需要10,000毫秒。 相對於輸入大小n的增加，我們現在的運行時間要長10倍。 現在，我們的運行時有了指數增長，而不是線性增長。 為了更好地理解不同的增長順序，我們將介紹Big-O表示法。

Big-O 複雜度圖表

big-o符號描述了當運行時趨於特定值或無窮大時算法的限制行為。 我們使用它根據算法對輸入大小變化的響應方式進行分類。 我們將輸入大小表示為n，將對輸入執行的操作數表示為N。我的示例將用Python編碼。

我們更喜歡在輸入方面或更快方面具有線性增長順序的算法，因為較慢的算法無法擴展到較大的輸入大小。 這是從最低到最高的運行時複雜度列表：

· O（1）：恆定時間複雜度

· O（log（n））：對數複雜度

· O（n）：線性複雜度

· O（n * log（n））：線性題複雜度

· O（n ^ k）：多項式複雜度（其中k> 1）

· O（c ^ n）：指數複雜度（其中c為常數）

· O（n！）：階乘複雜度

恆定時間複雜度：O（1）

如果運行時的值不受輸入大小的限制，則算法將在恆定時間內運行。

恆定時間算法的第一個示例是交換兩個數字的函數。 如果我們將函數定義更改為以一百萬個數字作為輸入，並且將函數主體保留不變，那麼它仍然只會執行相同的三個操作以及一個return語句。 運行時間不會根據輸入的大小而變化。

<code>
def
 
swapNums(num1, num2): 	
	
temp
 = 
num1 
	
num1
 = 
num2 
	
num2
 = 
temp 
	
return
 
(num1, num2)
/<code>

在第二個示例中，我們將首先檢查輸入消息是否為" Hello World！"。 並將消息更改為另一個值（如果是）。 之後，它將循環執行3次，然後執行另一個循環以將消息打印100次-意味著該消息總共被打印300次。 儘管進行了所有這些操作-由於該函數不會根據輸入大小執行更多操作-該算法仍會在恆定時間內運行。

<code>
 
def
 
printMessage300Times
(message)
:
 
	
if
(message == 
"Hello World!"
) 
    message = 
"Pick something more original!"
 
	
for
 x 
in
 range(
0
, 
3
): 
  	
for
 x 
in
 range(
0
, 
100
): 
    	print(message)/<code>

對數時間複雜度：O（log（n））

對數算法具有很好的可擴展性，因為當輸入大小n增加時，操作數N與輸入n大小的比率減小。 這是因為對數算法無法訪問其輸入的所有元素，正如我們在二分查找算法中所看到的那樣。

在二進制搜索中，我們嘗試在排序列表num_list中找到輸入數字num。 我們的輸入大小n是num_list的長度。

由於列表是經過排序的，因此我們可以將要搜索的數字與列表中間的數字進行比較。 如果num大於中點數，則我們知道num只能位於列表的較大一側-因此我們可以完全丟棄列表的下端並節省時間，而無需進行處理。

然後，我們可以在列表的較大部分上遞歸地重複此過程（其行為類似於循環），每次迭代時都將丟棄剩餘的num_list的一半。 這就是我們如何實現對數時間複雜度的方法。

<code>def binarySearch(num_list, left_i, right_i, num): 
	
if
 right_i >= left_i: 
  	midpoint = left_i + (right_i - left_i)/
2
 
    
if
 num_list[midpoint] == num: 
      
return
 midpoint 
    elif num_list[midpoint] > num: 
      
return
 binarySearch(num_list, left_i, midpoint-
1
, num) 
    
else
: 
      
return
 binarySearch(num_list, midpoint+
1
, right_i, num) 
	
else
: 
  	
return
 
"Number not in collection"
/<code>

線性時間複雜度：O（n）

當運行時間最多與輸入n的大小成比例增加時，算法以線性時間運行。 如果我們將輸入乘以10，則運行時也應乘以10或更少。 這是因為在線性時間算法中，我們通常在輸入的每個元素上運行操作。

在未排序的數字集合中查找最大值是一種可以在線性時間內運行的算法，因為我們必須檢查一次輸入中的每個元素才能解決該問題：

<code>def findMaxNum(list_of_nums): 
	
max
 = list_of_nums[
0
] 
	
for
 i 
in
 range(
1
, 
len
(list_of_nums.length)): 
  	
if
(list_of_nums[i] > 
max
): 
    	
max
 = list_of_nums[i] 
	
return
 
max
/<code>

在for循環中，我們遍歷輸入n中的每個元素，如果需要，在返回最後的最大值之前更新最大值。 線性時間算法的更多示例包括檢查無序列表中的重複項或查找列表的總和。

線性時間複雜度：O（n * log（n））

線性時間算法比線性時間算法稍慢，並且仍然可以擴展。

這是一種中等程度的複雜性，會在線性時間附近浮動，直到輸入達到足夠大的大小為止。 在線性運算時間內運行的算法的最流行示例是排序算法，例如mergeSort，quickSort和heapSort。 我們來看一下mergeSort：

<code>
def
 
mergeSort(num_list): 
	
if
 
len(num_list) > 1: 
  	
midpoint
 = 
len(arr)//2 
	
L
 = 
num_list[:midpoint] 
 
  
R
 = 
num_list[midpoint:] 
 
    

 
    

 
  
i
 = 
j = k = 0 
 
  
while
 
i < len(L) and j < len(R): 
  	
if
 
L[i] < R[j]: 
    	  = 
L[i] 
			 =
1 
		
else
: 

    	  = 
R[j]  

			 =
1 
			 =
1 
 
  
while
 
i < len(L): 
  	  = 
L[i] 
		 =
1 
		 =
1 
 
  
while
 
j < len(R): 
  	  = 
R[j] 
		 =
1 
		 =
1
/<code>

" mergeSort"的工作方式如下：

· 遞歸地劃分num_list，直到元素為兩個或更少

· 迭代地對每對項目進行排序

· 迭代合併結果數組

通過這種方法，我們可以實現線性運算時間，因為必須對整個輸入n進行迭代，並且必須發生O（log（n））次（輸入只能減半O（log（n））次）。 使n個項目遍歷log（n）次會導致運行時O（n * log（n）），也稱為線性時間。

多項式時間複雜度：O（n ^ c）其中c> 1

如果所有輸入大小n的運行時間增加相同的指數c，則算法將在多項式時間內運行。

這種時間上的複雜性以及隨後的複雜性無法擴展！ 這意味著隨著輸入大小的增加，運行時間最終將變得太長而無法使算法可行。 有時，我們遇到的問題無法用更快的方式解決，我們需要在如何限制輸入大小方面發揮創意，這樣我們就不會經歷多項式算法會耗費較長的處理時間。 多項式算法的示例是bubbleSort：

<code>
def
 
bubbleSort(num_list): 
	
n
 = 
len(num_list) 
	
for
 
i in range(n): 
 
    
for 
 
j in range(0, n-i-1): 
 
 
    	
if
 
num_list[j] > num_list[j+1] :
      	
temp
 = 
num_list[j] 
				  = 
num_list[j+1] 
				  = 
temp
/<code>

bubbleSort將一遍又一遍地遍歷列表中的所有元素，並在發現相鄰數字混亂時交換它們。 僅當發現所有數字的順序正確時，它才會停止。

在下面的圖片中，我們只有7個項目，並且可以對整個集合進行3次迭代以對數字進行排序-但如果是100個數字，則很容易看出運行時間會變得很長。 這沒有規模。

指數時間複雜度：O（c ^ n）其中c是常數

當運行時隨著輸入數據集的增加而加倍時，算法將以指數時間運行。 遞歸計算斐波那契數是指數時間算法的一個示例：

<code>
def
 
fibonacci
(n)
:
 
	
if
 n == 
0
: 
  	
return
 
0
 
	
elif
 n == 
1
: 
  	
return
 
1
 
	
else
: 
  	
return
 fibonacci(n
-1
) + fibonacci(n
-2
)/<code>

該算法在最後一行調用了兩次，一次是n-1，一次是n-2。 這意味著如果我們從n = 7開始，我們將總共調用該函數25次！ 隨著輸入的增長，運行非常昂貴。

階乘時間複雜度：O（n！）

最後，如果算法在輸入n上迭代等於n乘以所有小於n的正整數的次數，則它將在階乘時間內運行。 這是我們將在本文中討論的最慢的時間複雜度，主要用於計算集合的排列：

<code>
def
 
getListPermutation(items_list): 
	
results
 = 
[]  

	
i
 = 
0 
	
l
 = 
len(items_list) 
	
while
 
i < l: 
  	  
k = i, i + 1 
		
while
 
k <= l: 
    	  
".join(items_list[j:k])) 
			
k
 = 
k + 1 
			
i
 = 
i + 1 
	
print
 
results
/<code>

結論

謝謝閱讀！ 我很想聽聽您的意見或提出任何問題。

(本文翻譯自Cody Nicholson的文章《Complexity Theory for Algorithms》，參考：https://medium.com/better-programming/complexity-theory-for-algorithms-fabd5691260d)