时间复杂度与空间复杂度

时间复杂度

基础概念

def fun(n):
	sum=0
	for i in range(n+1):
		sum = sum + i
	return sum

假设每行代码执行时间一样，为unit_time，第2行分别需要1个unit_time时间，第3,4行执行了n遍，所以需要(2n+1)*unit_time时间
所有代码执行时间T(n)与每行代码执行次数成正比

def fun(n):
	sum=0
	for i in range(n+1):
		for j in range(n+1):
			sum = sum + i * j
	return sum

整段代码执行时间为：(2n²+n+1)*unit_time
T(n)=O(f(n))
T(n):代码执行时间，n表示数据规模
f(n):每行代码执行的次数总和，这是一个公式
O:表示正比
第一个例子：T(n)=O(2n+1)
第二个例子：T(n)=O(2n²+n+1)
这就是O时间复杂度表示法。
它并不具体表示代码真正执行时间，而是表示代码执行时间随数据规模增长的变化趋势，也叫渐进时间复杂度
当n很大时，常量，系数，低阶等可以忽略，只需要记录一个最大量级就可以了
第一例子：T(n)=O(n) 第二例子：T(n)=O(n²)

时间复杂度分析

1.只关注循环执行次数最多的一段代码
第一个例子：时间复杂度就是O(n)

2.加法法则：总复杂度等于量级最大的那段代码复杂度
第二个例子：时间复杂度就是O(n²)

3.乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
第二个例子：时间复杂度就是O(n²)

几种常见时间复杂度实例

1.常量阶 O(1)
2.对数阶 O(logn)
3.线性阶 O(n)
4.线性对数阶 O(nlogn)
5.平方阶 O(n²)、立方阶 O(n³)……k 次方阶 O(n^k)
6.指数阶 O(2ⁿ)
7.阶乘阶 O(n!)

常见多项式时间复杂度

1. O(1) 常量级复杂度：HashMap get()、put()
   代码执行时间不随n的增长而增长
2. O(logn)、O(nlogn)

i=1
while i<=n:
	i = i * 2

2^x=n
x = log₂n
时间复杂度为O(log₂n)，不管以2为低，还是以3为低，都可以将复杂度记为O(logn)
nlogn：

for i in range(n)
	while i < n:
		i = i * 2

3. O(m+1)、O(m*n)

def fun(m,n):
	sum_1 = 0;
	for i in range(m):
		sum_1 = sum_1 + i;
	sum_2 = 0;
	for j in range(n):
		sum_2 = sum_2 + j;
	return sum_1 + sum_2

空间复杂度

基础

空间复杂度就是渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系。

1. S(n)=O(1)：
   i = 1
2. S(n)=O(n)：
   list=[]

总结

O(1)、O(logn)、O(n)、O(nlogn)、O(n² )、O(2ⁿ)