• 微信公众号：美女很有趣。 工作之余，放松一下，关注即送10G+美女照片！

# Python 算法的时间复杂度和空间复杂度 (实例解析)

2小时前 1次浏览

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

``````>>> 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``````

F(2n)=F(n+1)*F(n)+F(n)*F(n-1) ; F(2n+1)=F²(n+1)+F²(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``````

``````>>> 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

### 常见的时间复杂度举例

``````>>> 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
>>> ``````

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

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

``````>>> 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]
>>> ``````

``````>>> 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``````

``````>>> 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
>>> ``````

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

## 空间复杂度

``````>>> 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]
``````

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

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

（本篇转换自同名博文的C语言版本）