Python 演算法的時間復雜度和空間復雜度 (實體決議)

如何衡量一個演算法的好壞呢？
一個演算法如果寫的十分的短，是不是就非常的好呢？

例如斐波那契數列：

def Fib(n:int)->int:
    if n<3: return 1
    return Fib(n-1)+Fib(n-2)

斐波那契數列的一般都使用數列定義的遞推公式來遞回，當n大于30時計算就非常吃力了；想要計算第100萬項的值基本上是不可能的了，

>>> from time import time
>>> for i in range(30,40):
	t=time();n=Fib(i);print(i,time()-t)

	
30 0.42186927795410156
31 0.6874938011169434
32 1.1093668937683105
33 1.7812433242797852
34 2.8906190395355225
35 4.640621185302734
36 7.48436975479126
37 12.109369277954102
38 19.6406192779541
39 31.74999499320984

用Fib(n-1)+Fib(n-2)遞回只能一項項往前推，太慢了；我樣可以這樣改進，用斐波數列的性質（如下所示）來遞回，效率明顯提升：計算第10萬項秒殺，第100萬項20秒以內，

由 F(1)=F(2)=1; F(n)=F(n-1)+F(n-2) 推匯出：

F(2n)=F(n+1)*F(n)+F(n)*F(n-1) ; F(2n+1)=F2(n+1)+F2(n)

>>> def Fib(n:int)->int:
    if n<3: return 1
    if n%2: return Fib(n//2)**2+Fib(n//2+1)**2
    return Fib(n//2)*(Fib(n//2+1)+Fib(n//2-1))

>>> from time import time
>>> t=time();n=Fib(100);print(time()-t)
0.0
>>> t=time();n=Fib(1000);print(time()-t)
0.015600204467773438
>>> t=time();n=Fib(10000);print(time()-t)
0.062400102615356445
>>> t=time();n=Fib(100000);print(time()-t)
0.9536018371582031
>>> t=time();n=Fib(1000000);print(time()-t)
18.566032886505127

此函式已知項只有F(1)、F(2)兩項，若增加已知項的項數也能提升一點效率，計算第100萬項的值只要3秒不到：

>>> def Fib(n:int)->int:
    if n<11: return [0,1,1,2,3,5,8,13,21,34,55][n]
    t=n//2
    if n%2: return Fib(t)**2+Fib(t+1)**2
    return Fib(t)*(Fib(t+1)+Fib(t-1))

>>> from time import time
>>> t=time();n=Fib(1000);print(time()-t)
0.0
>>> t=time();n=Fib(10000);print(time()-t)
0.017600059509277344
>>> t=time();n=Fib(100000);print(time()-t)
0.22040081024169922
>>> t=time();n=Fib(1000000);print(time()-t)
2.76320481300354
>>> 

那么我們要用什么方式去衡量一個演算法的好壞，所以我們引進了時間復雜度和空間復雜度， 時間復雜度主要衡量一個演算法的運行快慢，而空間復雜度主要衡量一個演算法運行所占用空間，

時間復雜度

時間復雜度的概念

衡量一個演算法的運行時間快慢也就是時間復雜度，那么計量的單位是什么？如果用我們常用的時間單位例如：秒、毫秒，這就存在一個問題，不同機器由于配置不同時間會不相同，而且要想知道時間就必須上機跑代碼很麻煩，所以我們把演算法花費的時間與其中陳述句執行次數成正比，演算法中的基本操作執行個數，為演算法的時間復雜度，

>>> def fun(n:int)->None:
	count = 0;
	for i in range(n):
		for j in range(n):
			count += 1
	for i in range(n*2):
		count += 1
	m = 10
	while m:
		count += 1
		m -= 1
	print(count)

	
>>> fun(10)
130
>>> fun(100)
10210
>>> 

count在這個函式中我們很容易知道執行了F(N)=N^2+2*N+10
其實我們在計算精確的執行次數，而只需要大概執行次數，這里我們使用大O的漸進表示法，

大O的漸進表示法

大O符號（Big O notation）：用于描述函式漸進行為的數學符號，
推導大O階方法：

用常數1取代運行時間中的所有加法常數
在修改后的運行次數函式中，只保留最高階項
如果最高階項存在且不是1，則去除與這個專案相乘的常數，得到的結果就是大O階
所以函式FUN的復雜度為：O(N^2)

常見的時間復雜度舉例

例一：

>>> def fun(m,n:int)->int:
	i = 0
	for j in range(m): i += 1
	for j in range(n): i += 1
	return i

>>> fun(10,50)
60
>>> fun(100,5000)
5100
>>> 

很明顯這里的時間復雜度是O(M+N)
其實如果M遠遠大于N則時間復雜度為O(M)
如果N遠遠大于M則時間復雜度為O(N)

例二：

>>> def fun(n:int)->int:
	i = 0
	for j in range(1000):
		i += 1
	return i

>>> fun(100)
1000
>>> fun(1000)
1000

時間復雜度為O(1000)但是如果為常數的話，時間復雜度可以直接寫為O(1)

例三：冒泡排序

>>> def Bubble(a:list)->None:
	for i in range(len(a)-1):
		for j in range(len(a)-1-i):
			if a[j]<a[j+1]:
				a[j],a[j+1]=a[j+1],a[j]

				
>>> b = [*range(1,6)]
>>> Bubble(b)
>>> b
[5, 4, 3, 2, 1]
>>> 

由這個程式我們可以知道F(N)=N-1+N-2+.....+1=(N^2-N)/2

例四：二分查找

>>> def binSearch(a:list,x:int):
	left,right = 0,len(a)
	while left<=right:
		mid = (left+right)//2
		if x>a[mid]:
			left = mid+1
		elif x<a[mid]:
			right = mid-1
		elif x==a[mid]:
			return mid
	return -1

>>> b = [1,2,3,4,5,6,7,8]
>>> for i in range(1,9):
	binSearch(b,i)

	
0
1
2
3
4
5
6
7

這個演算法對于每次查找，找不到就會將范圍縮小二倍，時間復雜度也就是O(log2 N)

例五：遞回階乘

>>> def F(n:int)->int:
	if n: return F(n-1)*n
	return 1

>>> F(0)
1
>>> F(1)
1
>>> F(2)
2
>>> F(3)
6
>>> F(4)
24
>>> F(5)
120
>>> 

這個也非常簡單return的 值為F(N-1)*F(N-2)........F(0)一共是N+1個，所以中間的代碼也就執行了N+1次，所以時間復雜度是O(N)

例六：斐波那契數列

def F(n:int)->int:
    if n<3: return 1
    return F(n-1)+F(n-2)

這里時間復雜度像一顆樹一樣展開，每一個節點會有兩個分支，所以是一個等比數列，從1一直到2^(n-2)次方的和2^(n-1)-1，但實際上要比這個小一點但是量級都是2^N,故時間復雜度為O(2^N)，

空間復雜度

空間復雜度也是一個數學運算式，是對一個演算法在運行程序中臨時占用儲存空間大小的度量，

空間復雜度不是程式占用了多少bytes空間，因為這個也沒太大意義，所以空間復雜度算的是變數的個數，也用O（）來表示，

注意：函式運行所需要的堆疊空間在編譯的時候就已經確認好了，因此空間復雜度主要通過函式在運行時顯示申請的空間來確定，

例一：冒泡排序

>>> def Bubble(a:list)->None:
	for i in range(len(a)-1):
		for j in range(len(a)-1-i):
			if a[j]<a[j+1]:
				a[j],a[j+1]=a[j+1],a[j]

實際上這里開辟的空間只有i，j 所以空間復雜度為O(1)，

例二：階乘函式

>>> def F(n:int)->int:
	if n: return F(n-1)*n
	return 1

首先答案是O(N)
這里如果對函式堆疊幀不是很了解的話，這個原理也就不會知道，函式堆疊幀可以簡單的理解為：函式每被呼叫一次，都會在堆疊區上開辟一塊空間，所以F(N)會呼叫F(N-1)，F(N-1)會呼叫F(N-2)…同時會呼叫N個F，每個F都會開辟一塊空間，所以空間復雜度為：O(N)，

示例三：斐波那契數列

def F(n:int)->int:
    if n<3: return 1
    return F(n-1)+F(n-2)

通過上面的實體我們就可以知道斐波那契數列實際上開辟了N個Fib函式空間，只是這些函式空間會被重復利用，總共被運行2^n-1次，所以空間復雜度為：O(N)，

（本篇轉換自同名博文的C語言版本）