如何衡量一个算法的好坏呢？
一个算法如果写的十分的短，是不是就非常的好呢？
例如斐波那契数列：
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)=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此函数已知项只有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语言版本）