NOIP学习小站在计算机科学中，算法的时间复杂度是一个函数，它定性描述该算法的运行时间。时间复杂度常用大O符号表述，一般描述为与问题规模\(n\)相关的函数\(O(f(n))\)，但不包括这个函数的低阶项和最高阶系数。
一、时间复杂度的定义
一个算法花费的时间与算法中基本语句的执行次数成正比例，哪个算法中基本语句执行次数多，它花费时间就多。一个算法中的基本语句执行次数称为语句频度或时间频度，记为\(T(n)\)。
一般情况下，算法中基本操作重复执行的次数是问题规模\(n\)的某个函数，用\(T(n)\)表示，若有某个辅助函数\(f(n)\),使得当\(n\)趋近于无穷大时，\(T(n)/f (n)\)的极限值为不等于零的常数，则称\(f(n)\)是\(T(n)\)的同数量级函数（大学高等数学知识），而\(O(f(n)) \)为算法的渐进时间复杂度，简称时间复杂度。
在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为\(O(1)\)或\(O(c)\)（\(c\)为常量），另外，在时间频度\(T(n)\)不相同时，时间复杂度\(O(f(n))\)有可能相同，如\(T(n)=n^2+3n+4\)与\(T(n)=4n^2+2n+1\)它们的频度不同，但时间复杂度相同（时间复杂度不考虑\(T(n)\)的低阶项和最高阶项系数），都为\(O(n^2)\)。
常见的时间复杂度有：\(O(1)\)、\(O(c)\)（\(c\)为常量）、\(O(\log{n})\)、\(O(n)\)、\(O(n\log{n})\)、\(O(m*n)\)、\(O(n^2)\)、\(O(n^3)\)、\(O(2^n)\)、\(O(n!)\)等。解决同一个问题的不同算法，时间复杂度越低，则算法效率越高。
二、时间复杂度的计算方法
根据定义，可以归纳出时间复杂度的基本计算步骤：
- 计算出基本操作的执行次数\(T(n)\)：
基本操作即算法中的每条语句（注意调用函数很特别，调用函数的语句往往不能简单认为是1次基本操作），语句的执行次数也叫做语句的频度。在做算法分析时，一般要考虑最坏的情况。 - 计算出\(T(n)\)的数量级：
求\(T(n)\)的数量级，只要将\(T(n)\)进行如下一些操作：忽略常量、低次幂，去掉最高次幂的系数，得到\(T(n)\)的数量级函数\(f(n)\)。 - 用\(O(f(n))\)来表示时间复杂度。
简而言之：如果一个算法的执行次数是 \(T(n)\)，那么只保留最高次项，同时忽略最高项的系数后得到函数\( f(n)\)，此时算法的时间复杂度就是 \(O(f(n))\)。
举一个例子来说明：
#include<iostream>
using namespace std;
int main()
{
int s1,s2,n,i,j;
s1 = 0;
s2 = 0;
cin>>n;
for(i=1;i<=n;i++){
s1 += i;
for(j=1;j<=n;j*=2){
s2 += j;
}
}
cout<<s1<<" "<<s2<<endl;
return 0;
} 程序5、6、7、8行语句的频度均为1，外层循环赋初值i=1频度为1，这部分总频度为5；
循环体中i<=n、s1+=i、j=1、i++，这4句执行次数均为\(n\)（严格计算的话，条件判断语句执行次数是\(n+1\)次），这部分总频度为\(4n\)；
内层循环中j<=n、s2+=j、j++，这3句执行次数均为\(n\log_2{n}\)（高中数学对数知识），这部分总频度为\(3n\log_2{n}\)；
第15、16行语句的频度为1，这部分总频度为2。
经过上面的分析，可知本程序\(T(n)=5+4n+3n\log_2{n}+2\)，整理得\(T(n)=3n\log_2{n}+4n+7\)，忽略掉\(T(n)\)中的常量、低次幂和最高次幂的系数，得到\(T(n)\)的数量级函数\(f(n) = n\log_2{n}\)，所以算法的时间复杂度是\(O(n\log_2{n})\)，可以再进一步简记为\(O(n\log{n})\)。
决定算法复杂度的是执行次数最多的语句，一般也是最内层循环的语句，上述步骤可以简化为：
- 找到执行次数最多的语句（要考虑最坏的情况）
- 计算该语句执行次数的数量级函数\(f(n)\)
- 用\(O(f(n))\)来表示算法时间复杂度
仍然以上述程序为例，执行次数最多的语句是内层循环体中的：s2 += j;，执行次数的数量级\(f(n)=n\log_2{n}\)，所以算法时间复杂度为：\(O(n\log_2{n})\)。
此外要注意：算法时间复杂度分析要考虑最坏的情况，以下面程序为例：
#include<iostream>
using namespace std;
int main()
{
int n,f;
cin>>n>>f;
for(int i=1;i<=n;i++){
if(f==0){
for(int j=1;j<=n;j++){
//...考虑最坏情况，这里是执行次数最多的语句
}
}else{
//...
}
}
return 0;
}最坏情况时（输入的f值为0），执行次数最多的是双重循环体中的语句，算法的时间复杂度为\(O(n^2)\)。
但是要注意，并不是出现循环，算法的时间复杂度就是\(O(n)\)、\(O(n*m)\)、\(O(n^2)\)之类的，也有可能是\(O(c)\)（\(c\)为常量），来看前面求“水仙花数”的程序：
#include<iostream>
using namespace std;
int main()
{
for(int i=100;i<=999;i++){
int g = i%10;
int s = i/10%10;
int b = i/100%10;
if(g*g*g+s*s*s+b*b*b==i) cout<<i<<" ";
}
return 0;
} #include<iostream>
using namespace std;
int main()
{
for(int b=1;b<=9;b++){
for(int s=0;s<=9;s++){
for(int g=0;g<=9;g++){
//百位上的数b，十位上的数s，个位上的数g
int n = b*100+s*10+g;
if(g*g*g+s*s*s+b*b*b==n) cout<<n<<" ";
}
}
}
return 0;
} 两段程序执行次数最多的语句都只执行900次，因此时间复杂度都是\(O(c)\)。
三、常见时间复杂度举例
1.\(O(1)\)或\(O(c)\)
前面计算\(\sum\limits_{i=1}^{n}i=1+2+3+...+n\)的结果，如果直接使用高中数学知识的等差数列求和公式\(\sum\limits_{i=1}^{n}i=\frac{n \times (n+1)}2\)，算法的时间复杂度是\(O(c)\)：
#include<iostream>
using namespace std;
int main()
{
int n;
cin>>n;
cout<<n*(n+1)/2<<endl; //n和n+1肯定有一个是偶数，n*(n+1)能被2整除
return 0;
}2.\(O(\log{n})\)
求解方法是用变量\(a\)追踪木棍的长度，循环中每次折半，那么算法的时间复杂度是\(O(\log_2{n})\)：
#include<iostream>
using namespace std;
int main()
{
int a,days = 1;
cin>>a;
while(a>1){
days ++;
a /= 2;
}
cout<<days;
return 0;
} 3.\(O(n)\)
仍然是上面累加求和的例子\(\sum\limits_{i=1}^{n}i\)，如果使用一重循环来累加求和，那么算法的时间复杂度是\(O(n)\)：
#include<iostream>
using namespace std;
int main()
{
int n,s = 0;
cin>>n;
for(int i=1;i<=n;i++) s += i;
cout<<s<<endl;
return 0;
}4.\(O(n\log{n})\)
对于1～\(n\)的每个正整数\(n_i\)，计算\(2^{x_i} \ge n_i\)的最小值\(x_i\)，如果不用\(cmath\)中的\(log2\)函数，可以这样编程：
#include<iostream>
using namespace std;
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++){
int j = 0,t = 1; //t用来保存\(2^j\)的结果
while(t<i){
t *= 2;
j++;
}
cout<<j<<endl;
}
return 0;
}执行次数最多的语句是内层循环的语句（并且是外层循环最后1次时），可知最大执行次数是\(n*\log_2{n}\) 次，那么算法的时间复杂度是\(O(n\log_2{n})\)。可以进一步优化算法，将时间复杂度降低到\(O(n)\)：
#include<iostream>
using namespace std;
int main()
{
int n,j = 0,t = 1; //t用来保存\(2^j\)的结果
cin>>n;
for(int i=1;i<=n;i++){
cout<<j<<endl;
if(i>=t) j++,t *= 2;
}
return 0;
}5.\(O(n*m)\)
输出\(n\)行\(m\)列由字符*拼成的字符矩形。借助双重循环实现，外层\(n\)次循环控制行数，内层\(m\)次循环控制每行字符数，那么算法的时间复杂度是\(O(n*m)\)：
#include<iostream>
using namespace std;
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++) cout<<"*";
cout<<endl;
}
return 0;
}6.\(O(n^2)\)
前面章节“阶乘累计求和”的例子，外层\(n\)次循环用来累加，内层\(i\)次循环计算\(i!\)：
#include<iostream>
using namespace std;
int main()
{
long long t,s = 0;
int n;
cin>>n;
for(int i=1;i<=n;i++){
t = 1;
for(int j=1;j<=i;j++) t *= j;
s += t;
}
cout<<s;
return 0;
} 执行次数最多的语句是内层循环的语句，可知执行次数是\(\sum\limits_{i=1}^{n}i = 1+2+3+...+n = \frac{n \times (n+1)}{2}\) 次，那么算法的时间复杂度是\(O(n^2)\)。当然可以进一步优化程序，降低算法的时间复杂度到\(O(n)\)：
#include<iostream>
using namespace std;
int main()
{
long long t = 1,s = 0;
int n;
cin>>n;
for(int i=1;i<=n;i++){
t *= i; //t是i!
s += t;
}
cout<<s;
return 0;
}7.\(O(n^3)\)
团队里有\(n\)位选手，每位选手都参加了\(n\)次训练，每次训练分为\(n\)次单元，现在给定每位选手每次训练每个单元的持续时间，计算所有选手平均单元训练时间。很显然，使用三重循环，在最内层循环体中输入数据并累加，那么算法的时间复杂度是\(O(n^3)\)：
#include<cstdio>
int main()
{
int n,m,s = 0;
scanf("%d",&n);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(int k=1;k<=n;k++){
scanf("%d",&m);
s += m;
}
}
}
printf("%.3f",1.0*s/(n*n*n));
return 0;
}