1. 算法效率
我们该如何判断一个算法的好坏？
衡量一个算法的好坏，是从时间和空间两个维度比较的，
而今天，我就来详细探讨一下时间复杂度。
2. 时间复杂度
2.1 时间复杂度的概念
时间复杂度是一个函数，
而：
算法中的基本操作的执行次数，为算法的时间复杂度。
我们当然不能只用运行一段程序的速度来解释时间复杂度，
毕竟每个人电脑的CPU运行速度不同。
例：
#include int main() { int n = 10; while (n > 0) { n--; } return 0; }
这一段代码走了10次，
他的时间复杂度是O(1)。
例2：
#include int main() { int n; scanf("%d", &n); while (n > 0) { n--; } return 0; }
这段代码走了n次，
他的时间复杂度是O(N)。
那么问题来了，时间复杂度究竟是怎么求的？
2.2 大O的渐进表示法
规则：
1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中，只保留最高阶项。
3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。
2.3 举例说明：
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); }
这段代码前面是2*N次，后面是10次，
加起来是2*N+10，
而他的时间复杂度是O(N)
例2：
冒泡排序的时间复杂度：
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; } }
冒泡排序最好的情况是O(N)，
而最坏的情况是要和每一个数比较交换，是O(N^2)。
所以他的时间复杂度是O(N^2)。
例3：
long long Fib(size_t N) { if (N < 3) return 1; return Fib(N - 1) + Fib(N - 2); }
斐波那契递归的时间复杂度是O(2^N)。
通过上述的例子，我们可以知道的是，
计算时间复杂度，计算的是该算法最坏的情况。
写在最后：
以上就是本篇文章的内容了，感谢你的阅读。
如果喜欢本文的话，欢迎点赞和评论，写下你的见解。
如果想和我一起学习编程，不妨点个关注，我们一起学习，一同成长。
之后我还会输出更多高质量内容，欢迎收看。
