引入

前面我们讲了普通赋值、输出、打印的时间复杂度、也讲了循环、嵌套循环的时间复杂度，现在我们来看看在函数引用下，时间复杂度有什么不同。

例子

看看下面程序的时间复杂度

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$)	指数阶