一、时间频度
定义：一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中语句的执行次数称为语句频度或时间频度，记为T(n).
实例：计算1~100的和。在这里插入图片描述
注：第一种方式，T(n)=n+1，其中+1，是最后一次对条件判断，不成立然后退出循环。
1、忽略常数项
在这里插入图片描述
结论：
1）2n + 20 和 2n 随着 n 变大，执行曲线无限接近，20可以省略。
2）3n + 10 和 3n 随着 n 变大，执行曲线无限接近，10可以省略。
2、忽略低次项
在这里插入图片描述
结论：
1）2n2+3n+10 和 2n随着n变大，执行曲线无限接近，可以忽略 3n+10
2）n2+5n+20 和 2n2随着n变大，执行曲线无限接近，可以忽略5n+20
3、忽略系数
在这里插入图片描述
可见，在趋向“无穷”时，前两组的曲线近乎是一条重合的直线。后两组的执行曲线出现了分离。
结论：
1）随着n值变大，5n2+7n 和 3n2+2n，执行曲线重合，说明这种情况下，5和3都可以忽略。
2）但n3+5n 和 6n3+4n ，执行曲线分离，说明多少次是关键。
二、时间复杂度
1、定义：
一般情况下，算法中的基本操作语句的重复执行次数是问题规模 n 的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当 n 趋近于无穷大时，T(n) / f(n) 的极限值为不等于0的常数，则称f(n) 是T(n) 的同
数量级函数。记作 T(n) = O( f(n) ) ，称 O( f(n) ) 为算法的渐近时间复杂度，简称时间复杂度。
注：T(n) 不同，但时间复杂度可能相同。
如T(n)=n2 +7n +6 和 T(n)=3n2+2n+2 它们的T(n)不同，但时间复杂度相同，都为O(n2).
2、计算方法
1）用常数 1 代替运行时间中的所有加法常数，T(n)=n2 + 7n + 6 => T(n)=n2 + 7n + 1
2）修改后的运行次数函数中，只保留最高阶项 T(n)=n2+7n+1 => T(n)=n2
3）去除最高阶项的系数 T(n) = n2 => T(n)= n2 => O(n2)
3、常见的时间复杂度
阶名 时间复杂度
常数阶 O(1)
对数阶 O(log2n)
线性阶 O(n)
线性对数阶 O(nlog2n)
平方阶 O(n2)
立方阶 O(n3)
k次方阶 O(nk)
指数阶 O(2n)
4、常见的时间复杂度对应的图
在这里插入图片描述
注：常见的算法时间复杂度由小到大依次为：
O(1) < O(log2n) < O(n) < O(nlog2n) < O(n2) < O(n3) < O(n k) < O(nk) < O(2n)
随着问题规模 n 的不断增大，以上时间复杂度不断增大，算法的执行效率也越低。所以，我们要尽可能避免使用指数阶的算法。
1）常数阶：O(1)
在这里插入图片描述
2）线性阶：O(n)在这里插入图片描述
3）对数阶：O(log2n)
在这里插入图片描述
4）线性对数阶：O(nlogN)
在这里插入图片描述
5）平方阶：O(n2)
在这里插入图片描述
6）立方阶（O(n3)、K次方阶（O(nk)）
说明：参考上面的O(n2) 去理解，O(n3)相当于三层n循环，其它的类似。
5、平均时间复杂度和最坏时间复杂度
1）平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，该算法的运行时间。
2）最坏情况下的时间复杂度称最坏时间复杂度。==一般讨论的时间复杂度都是最坏情况下的时间复杂度。==原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的界限，这就保证了算法的运行时间不会比最坏情况更长。