时间频度：
一个算法花费的时间与算法中语句的执行次数成正比，我们将算法中的语句执行次数称为语句频度或时间频度，记为T(n)，n称为问题的规模.
在时间频度中，当n不断变化时，时间频度T(n)也会不断变化，但有时我们想知道随着问题的规模n的不断增加，运行时间呈现怎样的变化规律，为此，引入了时间复杂度.
时间复杂度：
- 一般情况下，算法中基本操作重复执行的次数是问题规模
n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n) = O(f(n))，称O(f(n))为算法的时间复杂度. - 数学上定义：存在大于0的常数
C和非负整数n'，使得对于任意的n >= n'来说，T(n) <= C * f(n)，表示为T(n) = O(f(n)); - 简单来说：
O(n²)表示当n很大的时候，复杂度约等于C * n²，C是某个常数;
O(n)是说n很大的时候复杂度约等于C * n，C是某个常数. - 例如，
O(2n² + n + 1) = O (3n² + n + 3) = O (7n² + n) = O(n²)，一般都只用O(n²)表示就可以了.
时间复杂度n²比对
图中4条曲线分别表示4种不同的执行次数表达式，从图中可以看出，只要最高项的阶数相同，4种表达式值受其他项的影响很小，随着n增大，几乎可以忽略不计，甚至可以忽略与最高项相乘的常数
更通俗的讲：时间复杂度是
T(n)中受n的变化影响最大的那一项(不包含系数)
最坏时间复杂度和平均时间复杂度
最坏情况下的时间复杂度称最坏时间复杂度。一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。 这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会超过此时间.
常见时间复杂度
常数阶O(1)、对数阶O(log₂n)、线性阶O(n)、线性对数阶O(nlog₂n)、平方阶O(n²)、立方阶O(n³)、k次方阶(n)、指数阶O(2ⁿ)
常见时间复杂度比对图
从图中不难看出，选择算法时候应该尽量选择
对数阶而非指数阶时间复杂度的算法.
常数阶O(1)
void func(int n) {
printf("Hello, World!\n"); // 循环体时间复杂度为 O(1)
}
对数阶O(log₂n)
void func(int n) {
for(int i = 1; i < n; i *= 2) { // 循环次数为 log₂n
printf("Hello, World!\n"); // 循环体时间复杂度为 O(log₂n)
}
}
线性阶O(n)
void func(int n) {
for(int i = 0; i < n; i++) { // 循环次数为 n
printf("Hello, World!\n"); // 循环体时间复杂度为 O(n)
}
}
线性对数阶O(nlog₂n)
void func(int n) {
for(int i = 0; i < n; i++) { // 循环次数为 n
for(int j = 1; j < n; j *= 2) { // 循环次数为 log₂n
printf("Hello, World!\n"); // 循环体时间复杂度为 O(nlog₂n)
}
}
}
平方阶O(n²)
void func(int n) {
for(int i = 0; i < n; i++) { // 循环次数为 n
for(int j = 0; j < n; j++) { // 循环次数为 n
printf("Hello, World!\n"); // 循环体时间复杂度为 O(n²)
}
}
}
