一、嵌套循环的时间复杂度
1-1
//计算func1中++count语句总共执行了多少次? void func1(int N) { int count = 0; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) ++count; for (int k = 0; k < 2 * N; k++) ++count; int M = 10; while (M--) ++count; printf("%d\n", count); }
我们可以计算出其准确值为： 
写成一个跟N相关的函数式： 
即为时间复杂度的函数式
func1的基本操作次数：
N = 10 |
F(N) = 130 |
N = 100 |
F(N) = 10210 |
N = 1000 |
F(N) = 1002010 |
N越大，后两项对整个结果的影响就越小
简化这个表达式，只留下对结果影响最大的项
所以，这个嵌套循环的时间复杂度为：O（N^2）
要点
所以，实际中我们计算时间复杂度时，其实并不一定要计算精确的执行次数，而只需要大概执行次数， 那么这里我们使用大O的渐进表示法。 （类似于估算）
大O的渐进表示法
大O符号（Big O notation）： 是用于描述函数渐进行为的数学符号。推导大O阶的方法：
1.用常数1取代运行时间中的所有加法常数。 2.在修改后的运行次数函数中，只保留最高阶项。 3.如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。
这样列出来稍显抽象，理解起来也不够深刻
我们根据后面的例题来巩固理解到的方法
二、双重循环的时间复杂度
2-1
//计算func2的时间复杂度? void func2(int N) { int count = 0; for (int k = 0; k < 2 * N; k++) ++count; int M = 10; while (M--) ++count; printf("%d\n", count); }
精确计算值为：2N + 10
- 运行时间中没有常数。
- 保留最高阶项 - > 2N
- 最高阶存在且不为1，去除与之相乘的常数 - > N
最终取时间复杂度为：O(N)
2-2
//计算func3的时间复杂度? void func3(int N, int M) { int count = 0; for (int k = 0; k < M; k++) ++count; for (int k = 0; k < N; k++) ++count; printf("%d\n", count); }
func3的时间复杂度为：O（M+N）
注：一般情况下，时间复杂度计算时用的未知数都是N，但也可以是M、K、S......
若题目中给出条件,时间复杂度则为：
M >> N |
O(M) |
N >> M |
O(N) |
M、N接近 |
O(M)、O(N) |
三、常数循环的时间复杂度
3-1
//计算func4的时间复杂度? void func4(int N) { int count = 0; for (int k = 0; k < 100; k++) ++count; printf("%d\n", count); }
该循环次数为100次，在大O的渐进表示法中，用1取代常数次数
所以func4的时间复杂度是：O(1)
四、strchr的时间复杂度
4-1
//计算strchr的时间复杂度? const char* strchr(const char* str, int character);
strchr
用于在一个字符串中查找单个字符
要点
最好情况：任意输入规模的最小运行次数（下界）
平均情况：任意输入规模的期望运行次数
最坏情况：任意输入规模的最大运行次数（上界）
最好情况： 
次
平均情况： 
次
最坏情况： 
次
在实际中一般情况关注的是算法的最坏运行情况，所以strchr的时间复杂度为：O（N）
五、冒泡排序的时间复杂度
5-1
//计算BullleSort的时间复杂度? void BubbleSort(int* a, int n) { assert(a); for (size_t end = n; end > 0; --end) { int exchange = 0; for (size_t i = 1; i < end; ++i) { if (a[i - 1] > a[i]) { Swap(&a[i - 1], &a[i]); exchange = 1; } } if (exchange == 0) break; } }
过程
我们通过举简单的例子来算出BubbleSort的时间复杂度
这个算式其实就是一个等差数列，等差数列的前n项和公式为： 
结果
所以准确值为： 
因时间复杂度采用大O的渐进表示法，综上，BubbleSort的时间复杂度为;O(N^2)
六、二分查找的时间复杂度
6-1
//计算BinarySearch的时间复杂度? int BinarySearch(int* arr, int aim, int sz) { assert(arr); int left = 0; int right = sz - 1; while (left <= right) { int subscript = (left + right) / 2; if (arr[subscript] < aim) { left = subscript + 1; } else if (arr[subscript] > aim) { right = subscript - 1; } else { return subscript; break; } } if (left > right) return -1; }
二分查找的详细思路可以参照 - > 鹏哥二分法查找数组中元素
设数组的个数为N，查找的次数为X
计算时间复杂度，我们考虑最坏情况：该元素在头尾或找不到
正向
第一次查找，N/2；找不到
第二次查找，N/2/2;找不到
第三次查找，N/2/2/2；找不到
......
第X次查找，N一直除直到等于1。
表达式为： 
，所以查找次数X为： 
即BinarySearch的时间复杂度为：O( 
).
逆向
从1开始往回展开
这样展开直到结果等于数组元素个数N,查找次数X
1*2*2*2*......=N，即 
也算出了BinarySearch的时间复杂度为：O( 
).
七、递归算法的时间复杂度
递归算法的时间复杂度 = 递归次数 * 每次递归调用的次数
7-1
//计算阶乘递归Fac的时间复杂度? long long Fac(size_t N) { if (0 == N) return 1; return Fac(N - 1) * N; }
每次递归调用的次数为2，记为O（1）
递归次数为N，记为O(N)
所以Fac的时间复杂度为：O（N）
7-2
//计算斐波那契数列递归Fib的时间复杂度? long long Fib(size_t N) { if (N > 2) return Fib(N - 1) + Fib(N - 2); else return 1; }
斐波那契数列递归的分析
这样看下来，总共的递归次数像是一个等比数列求前n项和等比数列的前n项和公式：
所以， 
... 
整理得， 
且x远远小于2的n次方
综上，Fib的时间复杂度为：O（ 
）
