时间复杂度的认识
时间复杂度的定义
评价一个算法的运行速度（相对其它算法快或者慢），主要使用的方法是时间复杂度。
代码的时间复杂度主要取决于代码最多要执行的语句数量，通常用大O记号，描述的是最坏情况下代码的时间复杂度。
时间复杂度的计算在NOIP初赛中经常考到，而且在提高组中往往难度偏高语句数量的计算
语句计数规则
1）顺序结构中，一条语句记为1
2）选择结构中，看语句数量最多的那个分支中的语句数量
3）循环结构中，语句数量乘上循环次数
举例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;
int n, a[10005], cnt; // 语句计数+1
int main() {
cin >>n;
for(int i=1; i<=n; i++) { // 语句计数+n
cin >> a[i];
}
for(int i=1; i<=n-1; i++) { // 语句计数+n
for(int j=1; j<=n-i; j++) { // 语句计数+n
if(a[j] < a[j+1]) {
swap(a[j], a[j+1]); // 语句计数+1
cnt ++; // 语句计数+1
}
}
}
cout << cnt; // 语句计数+1
return 0;
}
语句总数量即为2n^2^ + n + 4
时间复杂度的规则
大O时间复杂度的计算： 1）只保留最高次项：2n^2 2）去掉最高此项的系数：n^2 3）语句数量套上O()：O（n^2）最后结果是O(n^2^)
如果最高次项是一个常数，那么时间复杂度直接记为O（1）
循环是重点
计算一个程序的时间复杂度时，可以主要看循环次数
如果代码没有循环，时间复杂度为O（1）
如果代码中有一个或多个循环，只需看循环次数最多的循环会循环多少次
每次循环具体执行的语句数量可以忽略不计
有趣的题目
设某算法的计算时间表示为递推关系式T(n) = T(n-1) + n （n为正整数），及T(0) = 1，则该算法的时间复杂度（ ）
A.O(logn) B.O(nlogn) C.O(n) D.O(n^2) 答案：D。可以把T（0）~ T（n）求出：
T(0) = 1
T(1) = 1 + 1
T(2) = 1 + 1 + 2
……
以此类推，T(n) = 1 + 1 + 2 + 3 + … + n
根据等差数列求和公式，T(n) = 1/2n^2^ + 1/2n + 1
时间复杂度即为O（n^2^）
总结
时间复杂度在算法中的应用是无穷的（若想继续了解时间复杂度欢迎阅读《算法导论》第二章），一定要牢牢掌握
CSP-J2021rp++！！！
