算法的复杂性理论

我们如何衡量算法的速度

复杂度理论是对算法运行所需时间量（取决于输入大小）的研究。 这对于软件开发人员理解非常有用，因此他们可以高效地编写代码。 有两种类型的复杂性：

空间复杂度：一个算法需要运行多少内存时间复杂度：一个算法需要运行多少时间。

通常我们比时间复杂度更担心时间复杂度，因为我们可以重用算法需要运行的内存，但是我们不能重用运行时间。 买内存比买时间要容易。 如果您需要更多内存-您可以从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)