时间复杂度与空间复杂度

为什么要有

确定我们的算法的效率

什么是

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

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

进一步可以分为

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

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

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

如何计算

计算步骤

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

例题

（1）给出下列代码语句的执行次数 ^[1]

int x = 91;
int y = 100;

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

（2）推导下列函数的时间复杂度

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)=\sum _{i=1}^{n-1}\sum _{j=i+1}^n\sum _{k=1}^{j}1$$$$T(n)=\sum _{i=1}^{n-1}\sum _{j=i+1}^{n}j$$

其中

$$\sum _{j=i+1}^{n}j=\frac{n(n-1)}{2}-\frac{j(j-1)}{2}=\frac{1}{2}(n^2-n+i^2-i)$$

故

$$T(n)=\frac{1}{2}\sum _{i=1}^{n-1}(n^2-n+i^2-i)$$$$T(n)=\frac{1}{2}((n-1)\times n^2+(n-1)\times n+\frac{n(n-1)(2n-1)}{6}+\frac{n(n-1)}{2})$$$$T(n)=\frac{n(n-1)(n+1)}{3}$$

所以时间复杂度为

$$O(n^3)$$

#Todo : 更多题目需要整理

常见时间复杂度

$O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(2^n)<O(n!)$

参考

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

---

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