一.前言
从这篇文章开始，C语言的学习就结束了，接下来将会开启数据结构与算法的学习。
早期，计算机刚被发明出来，内存空间并不是很大，所以不仅追求程序运行时的时间效率，还追求空间效率，但发展到今天，已经不太追求空间效率了，时间效率的追求是不变的。
下面就让我们一起学习时间复杂度和空间复杂度是什么吧~
二.时间复杂度
1.概念
1.时间复杂度是一个函数（注意这不是编程语言里的函数，而是数学意义上的函数）；
2.这个函数指的是算法跑的次数的函数，并不是算法运行的时间，因为同一个算法在不同的机器上运行的时间可能是不同的，用算法的运行时间表示时间复杂度是欠妥的；
3.一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。
二.大O的渐进表示法
概念：
大O符号（Big O notation）：是用于描述函数渐进行为的数学符号。
推导大O阶方法：
1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中，只保留最高阶项。
3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。
需要注意的是算法运行时可能会存在最好情况，最坏情况，平均情况，这个时候我们取最坏情况时的大O；
最坏情况：任意输入规模的最大运行次数(上界)
平均情况：任意输入规模的期望运行次数
最好情况：任意输入规模的最小运行次数(下界)
总结：
1.大O里的数就是函数表达式中对结果影响最大的项，或是最大的量级所在的项；
2.如果这个项的系数不是1，那么将它变成1，简单来说，这个项前面的系数得是1；
3.如果函数表达式是个常数，不管这个常数多大，都写成O( 1 )；
光说不练假把式，让我们通过例题来更好的理解上述所说吧~
三.常见时间复杂度计算举例
例1
1. // 请计算一下Func1中++count语句总共执行了多少次？ 2. void Func1(int N) 3. { 4. int count = 0; 5. for (int i = 0; i < N ; ++ i) 6. { 7. for (int j = 0; j < N ; ++ j) 8. { 9. ++count; 10. } 11. } 12. for (int k = 0; k < 2 * N ; ++ k) 13. { 14. ++count; 15. } 16. int M = 10; 17. while (M--) 18. { 19. ++count; 20. } 21. printf("%d\n", count); 22. }
不难看出：
Func1 执行的基本操作次数 ：
F(N)=N^2+2^N+10
N = 10 F(N) = 130
N = 100 F(N) = 10210
N = 1000 F(N) = 1002010
显然最大的量级是 N^2
所以时间复杂度为O(N^2)
例2
1. // 计算Func2的时间复杂度？ 2. void Func2(int N) 3. { 4. int count = 0; 5. for (int k = 0; k < 2 * N ; ++ k) 6. { 7. ++count; 8. } 9. int M = 10; 10. while (M--) 11. { 12. ++count; 13. } 14. printf("%d\n", count); 15. }
F(N)=2*N+10
影响最大的项为2*N，因为它的系数不是1，所以要变成1，即
时间复杂度：O(N)
例3
1. // 计算Func3的时间复杂度？ 2. void Func3(int N, int M) 3. { 4. int count = 0; 5. for (int k = 0; k < M; ++ k) 6. { 7. ++count; 8. } 9. for (int k = 0; k < N ; ++ k) 10. { 11. ++count; 12. } 13. printf("%d\n", count); 14. }
F(N)=M+N
由于并未明确告知M和N的关系，所以时间复杂度：O(M+N)
若M远大于N，则为O(M);
若N远大于M，则为O(N);
若亮着差不多大，则为O(N)或O(M);
例4
1. // 计算Func4的时间复杂度？ 2. void Func4(int) 3. { 4. int count = 0; 5. for (int k = 0; k < 100; ++ k) 6. { 7. ++count; 8. } 9. printf("%d\n", count); 10. }
F(N)=100
这是一个常数，所以时间复杂度：O(1)
例5.计算冒泡排序的时间复杂度
1. // 计算BubbleSort的时间复杂度？ 2. void BubbleSort(int* a, int n) 3. { 4. assert(a); 5. for (size_t end = n; end > 0; --end) 6. { 7. int exchange = 0; 8. for (size_t i = 1; i < end; ++i) 9. { 10. if (a[i-1] > a[i]) 11. { 12. Swap(&a[i-1], &a[i]); 13. exchange = 1; 14. } 15. } 16. if (exchange == 0) 17. break; 18. } 19. }
最好情况：
原本已排好序，所以进入第二个for循环时不进入if语句，所以exchange==0，直接跳出循环，所以时间复杂度：O(N)
最坏情况：
执行完了所有的循环，所以时间复杂度：O(N^2)
取最坏情况，所以最终的时间复杂度为：O(N^2)
如果没有exchange相关语句，那么最好情况和最坏情况都是O(N^2)
