算法性能评估

一、时间复杂度

规模：数据的大小对算法至关重要，绝对的影响运行时间

测试环境：环境的快慢对算法至关重要

1.1、大O表示法

def tmp(n):
	add = 0     <== 1*unit
	for i in range(n): <== n*unit
		add += i	<== n*unit
	return add

假设运行一行代码的时间记为1unit

运行T(n)=(2n+1)*unit

T(n)=O(f(n))，O表示T(n)与f(n)成正比，即算法的运行时间与数据规模成正比

O表示渐近时间复杂度

表示代码执行时间随数据规模增长的变化趋势

当n很大时，低阶、常量、系数三部分并不左右增长趋势，所以都可以忽略，就可以记为：T(n)=O(n)、T(n)=O(n²)

只关注循环次数多的代码

def tmp(n):
	add = 0
	for i in range(n):
		add += i
	return add

复杂度：O(n)

选大量级

def tmp(n):
	for i in range(999):
		print(123)
	
	for i in range(n):
		print(1)
	
	for i in range(n):
		for j in range(n):
			print(2)

复杂度：O(n²)

嵌套循环要乘积

def a(n):
	for i in range(n):
		print('c')

def tmp(n):
	for i in range(n):
		a(i)

复杂度：O(n²)

1.2、常见复杂度分析

非多项式量级(过于低效)：O(2ⁿ)和O(n!)

多项式量级：O(1)、O(logn)、O(nlogn)、O(n^k)

O(1)

代码不随着规模而增加

a=2
b=3
c=4

O(logn)

def tmp(n):
	i = 1
	while i < n:
		i = i * 2

i=2、2²、2³…2ⁿ

退出循环的条件是：2^x=n，即x=log₂ⁿ，时间复杂度为O(log₂ⁿ)

def tmp(n):
	i = 1
	while i < n:
		i = i * 3

log₃ⁿ就等于log₃² * log₃ⁿ，所以O(log₃ⁿ)=O(C * log₂ⁿ)，其中log₃²是一个常量。基于我们前面的理论：在采用大O标记复杂度的时候，可以忽略系数，即O(Cf(n))=O(f(n))。所以，O(log₂ⁿ)就等于O(log₃ⁿ)。因此，在对数阶时间复杂度的表示方法里，我们忽略对数的“底”，统一表示为O(logⁿ)。

O(m+n)、O(m*n)

def tmp(m, n):
	for i in range(m):
		print(1)
	
	for i in range(n):
		print(2)

二、空间复杂度

渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系。类比一下，空间复杂度全称就是渐进空间复杂度(asymptotic space complexity)，表示算法的存储空间与数据规模之间的增长关系。

def tmp(n):
	a = [1] * n
	for i in a:
		print(i)

第二行是O(n)