0%

理解算法时间复杂度和空间复杂度

发表于 更新于

时间复杂度

理解:某块代码的执行次数随变量n的变化
常用的时间复杂度量级

  • 常数阶O(1)
  • 对数阶O(logN)
  • 线性阶O(n)
  • 线性对数阶O(nlogN)
  • 平方阶O(n²)
  • 立方阶O(n³)
  • K次方阶O(n^k)
  • 指数阶O(2^n)

常数阶O(1)

无循环等复杂结构，无论代码执行多少行，时间复杂度都是O(1) 

1
2
3
4
int i=0;
int j=1;
i=j;
j==

对数阶O(logN)

代码执行次数=logN 

1
2
3
4
int i = 1;
while(i < n){
	i = i*2
}

线性阶O(n)

1
2
3
for(int i=0; i<=n; i++){
	j=i;
}

线性对数阶O(nlogN)

对数阶O(logN)基础上循环n次

1
2
3
4
5
6
for(int m=1; m<n; m++){
	int i = 1;
	while(i < n){
		i = i*2
	}
}

平方阶O(n²)

线性阶O(n)两层循环

1
2
3
4
5
for(int i=0; i<=n; i++){
	for(int j=0; j<=n; j++){
		s=j;
	}
}

立方阶O(n³)

线性阶O(n)三层循环

K次方阶O(n^k)

类推，K次方阶O(n^k) 相当于k层循环

指数阶O(2^n)

1
2
3
4
5
6
7
public void func(int n){
	if(n>1){
		return func(n-1)+func(n-2)
	}else{
		return 1
	}
}

解释： T(0)=T(1)=1, T(n)=T(n-1)+T(n-2)+1, 是一个斐波那契数列，时间复杂度为O((5/3)^n)，简化后O(2^n)
斐波那契数列没具体看，网上查别人的说法

空间复杂度

理解：存储空间随变量n的变化
和时间复杂度类似，存储空间与n无关空间复杂度为O(1),线性相关空间复杂度为O(n),同理还有O(n²)、(logN)等