时间复杂度

                                         时间复杂度

1 定义：时间复杂度是指执行算法所需要的计算工作量；
2 时间复杂度的计算：计算机运行一次代码要执行一次运算，例如：
int aFunc(void) {
printf(“Hello, World!\n”); // 需要执行 1 次
return 0; // 需要执行 1 次
}需要执行两次

int aFunc(int n) {
for(int i = 0; i<n; i++) { // 需要执行 (n + 1) 次
printf(“Hello, World!\n”); // 需要执行 n 次
}
return 0; // 需要执行 1 次
}则需要执行2n+2次

如果运行代码需要执行的次数是常数的话，常数对函数的影响不大，所以我们称这个时间复杂度为o（1）；如果是n^ 2+n+c 则时间复杂度为o（n^2），一般来说，如果一个算法的执行次数是t(n),那么只保留他的最高次幂项，同时忽略最高次幂的系数，得到f（n），那么时间复杂度为o（f（n））；

3 四个法则
3.1 单个循环体法则
对于一个循环，假设循环体的复杂度为o（n），循环次数为m，则这个循环的时间复杂度为o（n*m）；

3.2 多个循环体法则
假设循环体的复杂度为o（n），循环次数为m，t则这个循环的时间复杂度为o（nmt）；

3.3 多个时间复杂度
选择所有复杂度中最大的那个， max(O(n ^ 2)，O(n))，即 O(n^2)。

3.4 条件语句的推导
选择路径中最大的时间复杂度