Skip to content

时间复杂度与空间复杂度 ​

为什么要有 ​

确定我们的算法的效率

什么是 ​

时间复杂度:算法运行时间与数据量的关系

更加具体的来说,时间复杂度是操作数量(代码执行条数)T(n)的渐进上界,表示为O(f(n))​

进一步可以分为

  • 最差时间复杂度:给出了效率下限,通常使用这个
  • 最佳时间复杂度:不要使用
  • 平均时间复杂度:有些算法难以计算

空间复杂度:算法占用内存与数据量的关系

一般只关注最差时间复杂度

如何计算 ​

计算步骤 ​

  1. 统计操作数量
  2. 忽略常数项和系数
  3. 循环嵌套时使用乘法

例题 ​

(1)给出下列代码语句的执行次数 [1]

java
int x = 91;
int y = 100;

while(y > 0){
    if(x > 100) {
        x = x - 10; 
        y--;  // a
    } else {
        x++;  // b
    }
}

(2)推导下列函数的时间复杂度

java
void f(int n){
    for(int i=1; i<=n-1; i++){
        for(int j=i+1; i<=n; j++){
        	for(int k=1; i<=j; k++){
        		a++;
    		}
    	}
    }
}

解:

T(n)=∑i=1n−1∑j=i+1n∑k=1j1T(n)=∑i=1n−1∑j=i+1nj

其中

∑j=i+1nj=n(n−1)2−j(j−1)2=12(n2−n+i2−i)

故

T(n)=12∑i=1n−1(n2−n+i2−i)T(n)=12((n−1)×n2+(n−1)×n+n(n−1)(2n−1)6+n(n−1)2)T(n)=n(n−1)(n+1)3

所以时间复杂度为

O(n3)

#Todo : 更多题目需要整理

常见时间复杂度 ​

O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(2n)<O(n!)

参考 ​

https://www.hello-algo.com/chapter_computational_complexity/time_complexity/#232


  1. a执行100次,b执行1000次,两条语句一共执行1100次 ↩︎

Released under the MIT License.