引入
前面我们讲了普通赋值、输出、打印的时间复杂度、也讲了循环、嵌套循环的时间复杂度，现在我们来看看在函数引用下，时间复杂度有什么不同。
例子
看看下面程序的时间复杂度
int i; //执行1次
for(i=0;i<n;i++){
function(i);
}
// for 循环，复杂度为 O(n)
void function(int count){
printf("%d\n",count);
}
// 函数就执行了一个 printf 语句 复杂度位 O(1)
上面的循环语句，每执行一次，就会调用一次函数，函数是 1，循环 n 次 1 ，所以上面这个例子的时间复杂度是 O(n) 。
我们再来个复杂点的
int i; //执行1次
for(i=0;i<n;i++){
function(i);
}
// for 循环，复杂度为 O(n)
void function(int count){
int j;
for (j=0;j<n;j++){
printf("%d",j);
}
}
// 函数内是一个循环，随着 count 的增加，循环次数减少
这样一来，for 循环调用函数 n 次，每次函数内都执行 (n+1)/2 次循环。和之前的例子一样$n(n+1)/2=n^2/2+n/2$，根据时间复杂度三个法则，保留最高项，去掉非1最高项的乘数。那结果就是$O(n^2)$。
我们再提升一下难度：
int i; //执行1次
for(i=0;i<n;i++){
function(i);
}
// for 循环，复杂度为 O(n)
void function(int count){
int j;
for (j=count;j<n;j++){
printf("%d",j);
}
}
// 函数内是一个循环，随着 count 的增加，循环次数减少
n++;
//执行 1次
function(n);
//调用一次函数，函数包含循环，O(n)
for(i=0;i<n;i++){
function(i);
}
// 调用 n 次函数，n 次 n 次循环，O(n^2)
for(i=0;i<n;i++){
for(j=i;j<n;j++){
printf("%d",j);
}
}
// 跟之前一样，j 越来越大，内循环执行次数越来越少，O(n^2)
所以就是
$1+n^2+1+n+n^2+n^2=3n^2+n+2$
根据三法则
- 去掉加的常数：$3n^2+n$
- 只保留最高阶：$3n^2$
- 去掉非1最高阶的乘数：$n^2$
- 答案是：$n^2$
常见时间复杂度
上面的三个例子，我们对时间复杂度应该有了基本认识，我们来看看常见的时间复杂度。
| 例子 | 时间复杂度 | 术语 |
|---|---|---|
| $123456$ | O(1) | 常数阶 |
| $3n+4$ | O(n) | 线性阶 |
| $3n^2+4n+5$ | O($n^2$) | 平方阶 |
| $3log(2)n+4$ | O($logn$) | 对数阶 |
| $2n+3nlog(2)n+14$ | O($nlogn$) | nlog阶 |
| $n^3+2n^2+4n+5$ | O($n^3$) | 立方阶 |
| $2^n$ | O($2^n$) | 指数阶 |
我们来看看图
从这个图中，我们可以很清楚的看到：
- **常数阶和线性阶：**常数阶因为是一条直线，一开始比对线性阶要差。但是线性阶的斜率不为0，是缓慢增加的，所以随着输入规模增大，线性阶就不如常数阶那么好用了。
- **常数阶和对数阶：**跟线性阶一样，对数阶的斜率要小，所以爬升速度慢，但也在起步落后的情况下，超过了常数阶。
- **Nlog 阶和平方阶：**之前的图觉得 nlog 阶一枝独秀，增长非常快，但发现平方阶爬升速度更快。
- **立方阶：**立方阶爬升速度已经石井人的了。
- **立方阶和指数阶：**我们单独把这两个爬升最快拿出来，发现原来速度很快的立方阶，也远远赶不上指数阶。
所以，根据上面的表格和折线，我们总结出如下规律
O( 1 ) < O( log n ) < O(n)< O( nlogn )
O( nlogn ) < O( $n^2$ ) < O( $n^3$ ) < O( $2^n$ )
O( $2^n$ ) < O( $n!$ ) < O( $n^n$ )
再强调一次，我们不是要追求最大，这里的数值表示的是随着输入规模增大后，计算所需要的步骤，所以步骤越少越好。
尾巴
这是我的个人学习笔记，主要是应付考研复习使用，充斥着一些吐槽和个人观点，并不严谨，欢迎大家参考、指正。
评论