算法复杂度介绍

文章目录

算法复杂度中大O的意义
简单的复杂度分析
- 关于O(logn)
递归算法的复杂度分析
- 在递归中只做了一次递归调用
- 在递归中做了多次递归调用
最好/最坏/平均/均摊复杂度分析

算法复杂度中大O的意义

复杂度分析是估算算法执行效率的方法，公式O(f(n))表示算法的复杂度，此方法即为大O复杂度表示法O(f(n))中n表示数据规模，f(n)表示运行算法所需要执行的指令数。

估算下面的代码的执行效率

sum=0
for i in range(1,n+1):
	sum+=i
return sum
1
2
3
4

假设每行代码执行的时间都一样为t：

执行第一行代码需要时间t，第二三行代码运行了n遍，需要的时间为2n*t
这段代码总执行时间为（2n+1）*t

sum=0
for i in range(1,n+1):
	for j in range(1,n+1):
		sum+=i*j
return sum
1
2
3
4
5

假设每行代码执行的时间都一样为t：

执行第一行代码需要时间t，第二行代码运行了n遍，需要的时间为n*t
第三四行代码运行了n2次，需要时间2n2*t
这段代码总执行时间为（2n2+n+1）*t

大O复杂度表示法
T(n)=O(f(n)),O表示代码的执行时间T(n)与f(n)表达式成正比
大O复杂度表示法：上门例子中的T(n)=O（2n+1）,另一个T(n)=O（2n2+n+1）
大O时间复杂度并不表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，也叫做渐进时间复杂度，简称时间复杂度。
用大O表示法表示上面两段代码的时间复杂度，可以记为O(n)，O(n2)。

如果想在一秒之内解决问题：
O(n)的算法可以处理大概104级别的数据
O(n2)的算法可以处理大概108级别的数据
O(nlogn)的算法可以处理大概107级别的数据

空间复杂度
解决问题时，多创建了一个数据，O(n)
解决问题时，多创建了一个二维数据，O(n2)
解决问题时，用到了几个临时变量，O(1)
在这里插入图片描述

简单的复杂度分析

当两段代码的数据规模不同时，不能省略复杂度低的部分

sum_ = 0
for i in range(1，n+1):
    sum_ = sum_ + i
sum_1 = 0
for i in range(1,m+1):
    for j in range(m):
        sum_1 = sum_1 + i*j
return sum_+sum_1
1
2
3
4
5
6
7
8

上面的代码分为两部分，分别是求 sum_、sum_1
计算sum_部分的代码段时间复杂度O(n)，计算sum_1部分的代码段时间复杂度为O(m2)
总的时间复杂度由复杂度最大的部分决定, 所以上面代码复杂度为O(m2+n)

看见双重for循环，算法的复杂度一定是O(n2)么？

for i in range(n):        
	for j in range(100):            
		print(… …)    
return 0
1
2
3
4

时间复杂度为O(n)

关于O(logn)

def binary_search(alist, data):
    n = len(alist)
    first = 0    
    last = n - 1    
    while first <= last:
         mid = (last + first) // 2        
         if alist[mid] > data:            
         	last = mid - 1       
         elif alist[mid] < data:            
         	first = mid + 1        
         else:            
         	return True    
 	return False

1
2
3
4
5
6
7
8
9
10
11
12
13
14