0%

算法复杂度理解

发表于 更新于 分类于

算法复杂度分为时间复杂度，空间复杂度

时间复杂度：指执行当前算法所消耗的时间
空间复杂度：指执行当前算法所需要占用的内存空间

时间复杂度

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

我们假设一行代码执行时长为1，那么总时长为2+n,这个算法的耗时随着n的增加而增加，用时间复杂度表示为：O(n)

常见的时间复杂度量级有：

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

常数阶O(1)

无循环的代码，执行一次就完了
1
2
3
int i = 0;
i++;
print(i);

对数阶O(logN)

执行时长成对数上涨
1
2
3
4
int i = 1;
while(i<n){
   i = i*2;
}

线性阶O(n)

执行一下循环
1
2
3
4
int j = 1;
for(int i=1;i<=n;i++){
    j+=i;
}

线性对数阶O(nlogN)

简单的线性+对数叠加
1
2
3
4
5
6
int j = 1;
for(int i=1;i<=n;i++){
    while(j<n){
       j = j*2;
    }
}

平方阶O(n²)

两层循环
1
2
3
4
5
6
int m = 0;
for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
       m += i+j;
    }
}

立方阶O(n³)

3层循环

m次方阶O(nⁿ)

n层循环

指数阶O(2^n)

递归函数执行时长
1
2
3
4
5
6
7
long aFunc(int n) {    
     if (n <= 1) {        
         return 1;
     } else {        
         return aFunc(n - 1) + aFunc(n - 2);
     }
 }

空间复杂度

空间复杂度算法包括：

  1. 程序本身所占的空间
  2. 输入数据所占的空间
  3. 辅助变量所占的空间

常数阶O(1)

与变量无关，具体固定的空间占用
1
2
3
for(int i = 1; i<=n ; i++){
    i+=1;
}

线性阶O(n)

分配的空间与变量n相关，随着n的变化而变化
1
2
3
4
5
6
void fun(int n){
 int a[] = new int[n]
 for(int i = 1; i<=n ; i++){
       a[i]=i;
  }
}