小记

我们把 算法需要执行的运算次数用 n 的函数 表示，即 T(n) 。
为了 评估算法需要的运行时间 ，简化算法分析，引入时间复杂度的概念：用来度量算法的运行时间，记作: T(n) = O(f(n))。它表示随着 输入大小n 的增大，算法执行需要的时间的增长速度可以用 f(n) 来描述。

1.常数项对函数的增长速度影响并不大，所以当 T(n) = c，c 为一个常数的时候，那么这个算法的时间复杂度为O(1)；如果 T(n) 不等于一个常数项时，直接忽略常数项。

2.高次项对于函数的增长速度的影响是很大的。n^3 的增长速度是远超 n^2 的，同时 n^2 的增长速度是远超 n 的。 同时因为要求的精度不高，所以我们直接忽略低次项与常数：
T(n) = n^3 + n^2 + n + 1，此时时间复杂度为 O(n^3)。
也可以理解为只取最高项，，同时忽略它的系数，那就是最复杂的计算过程

3.假设一个循环，循环体的时间复杂度为 O(n)，循环次数为 m，则这个
循环的时间复杂度为O(n×m)：

//例1
void test(int n) {
for(int i = 0; i < n; i++) { // 循环次数为 n
printf(“Hello, World!\n”); // 循环体时间复杂度为 O(1)
}
//则该时间复杂度为 O(n × 1)，即 O(n)
}

//例2
void test(int n) {
for(int i = 0; i < n; i++) { // 循环次数为 n
for(int j = 0; j < n; j++) { // 循环次数为 n
printf(“Hello, World!\n”); // 循环体时间复杂度为 O(1)
}
//此时时间复杂度为 O(n × n × 1)，即 O(n^2)
//分析这种嵌套循环，应从循环内开始，由内而外地分析
}
}

4.对于顺序执行的语句或者算法，总的时间复杂度等于其中最大的时间复杂度。
//例1
void test(int n) {
// 第一部分时间复杂度为 O(n^2)
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
printf(“Hello, World!\n”);
}
}
// 第二部分时间复杂度为 O(n)
for(int j = 0; j < n; j++) {
printf(“Hello, World!\n”);
}
//此时时间复杂度为 max(O(n^2), O(n))，取最大那个，即 O(n^2)
}

5.对于条件判断语句，总的时间复杂度等于其中 时间复杂度最大的路径 的时间复杂度,跟第四点差不多，都是取最大那个
//例1
void test(int n) {
if (n >= 0) {
// 第一条路径时间复杂度为 O(n^2)
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
printf(“输入数据大于等于零\n”);
}
}
} else {
// 第二条路径时间复杂度为 O(n)
for(int j = 0; j < n; j++) {
printf(“输入数据小于零\n”);
}
}
//此时时间复杂度为 max(O(n^2), O(n))，即 O(n^2)
}