【解密算法：时间与空间的博弈】（上）：https://developer.aliyun.com/article/1424858
实例三：
// 计算Func4的时间复杂度？ void Func4(int N) { int count = 0; for (int k = 0; k < 100; ++k) { ++count; } printf("%d\n", count); }
- 循环：for (int k = 0; k < 100; ++k)
这个循环总共执行了 100 次。
循环内部只有一个基本操作 ++count。
因此，总的基本操作数可以表示为：100。
在大O符号表示法中，我们通常关注最高阶的项，而忽略低阶项和常数系数。在这种情况下，最高阶项是 100。
因此，Func4 函数的时间复杂度可以表示为 O(1)。
实例四：
// 计算strchr的时间复杂度？ const char* strchr(const char* str, int character);
strchr 函数用于在给定字符串中查找第一个出现的指定字符，并返回该字符后的部分字符串。
- 最好情况：1次找到
- 平均情况：N/2次找到
- 最坏情况：N次找到
在一般情况下，strchr 函数的时间复杂度可以被认为是 O(N)，其中 N 是输入字符串的长度。这是因为 strchr 需要遍历字符串中的每个字符来查找指定字符。在最坏情况下，它可能需要遍历整个字符串才能找到目标字符。
实例五：
// 计算BubbleSort的时间复杂度？ 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 是一种基本的排序算法，其时间复杂度取决于待排序数组的初始状态。让我们分析一下 BubbleSort 的时间复杂度。
BubbleSort 的主要思想是在每一轮遍历中，比较相邻的两个元素，如果顺序不对就交换它们，直到最大（或最小）元素“冒泡”到正确的位置。在每一轮遍历中，至少会将一个元素放置在其最终的位置上。
最坏情况下，数组完全逆序，需要执行 N-1 轮比较和交换操作。第一轮中，需要比较和可能的交换 N-1 次；第二轮中，需要比较和可能的交换 n-2次...
所以，总的操作次数为：(N-1) * N / 2 = N * N / 2 - N / 2
在大O符号表示法中，我们通常关注最高阶的项，而忽略低阶项和常数系数。在这种情况下，最高阶项是 n^2。因此，BubbleSort 的时间复杂度可以表示为 O(n^2)。
需要注意的是，BubbleSort 的平均和最坏情况下的时间复杂度都是 O(N^2)，即使在最好情况下，数组已经是有序的，BubbleSort 也需要进行 n-1 轮比较，时间复杂度都是 O(N)。
实例六：
// 计算BinarySearch的时间复杂度？ int BinarySearch(int* a, int n, int x) { assert(a); int begin = 0; int end = n - 1; // [begin, end]：begin和end是左闭右闭区间，因此有=号 while (begin <= end) { int mid = begin + ((end - begin) >> 1); if (a[mid] < x) begin = mid + 1; else if (a[mid] > x) end = mid - 1; else return mid; } return -1; }
BinarySearch（二分查找）是一种高效的查找算法，它的时间复杂度为 O(log N)，其中 N 是待查找数组的长度。
在每一轮循环中，BinarySearch 将当前搜索范围缩小为原来的一半。假设当前搜索范围的长度为 len，在下一轮循环中，搜索范围的长度将减半为 len/2。因此，每一轮循环都可以排除一半的元素。
最坏情况下，当搜索范围缩小到只有一个元素时，算法结束。而要将 n 个元素缩小到 1 个元素，需要进行 log₂(n) 次操作。
因此，BinarySearch 的时间复杂度是 O(log n)。
BinarySearch 在已排序的数组中查找元素，通过不断缩小搜索范围，每次排除掉一半的元素，因此它的时间复杂度非常低。
图解：
实例七：
// 计算阶乘递归Fac的时间复杂度？ long long Fac(size_t N) { if (0 == N) return 1; return Fac(N - 1) * N; }
阶乘递归函数 Fac 的时间复杂度可以通过递归关系来分析。在这种情况下，递归的深度与输入规模 N 相关，每一层递归都会进行一次乘法操作。让我们分析一下：
第一递归层（N = N）：执行 1 次 Fac(N - 1) * N乘法。
第二递归层（N = N-1）：执行 1 次 Fac(N - 2) * N乘法。
第三递归层（N = N-2）：执行 1 次 Fac(N - 1) * N乘法。
...
最后一层递归（N = 0）：执行 1 次 Fac(0) * N乘法。
总的乘法操作次数为 N 次。
因此，阶乘递归函数 Fac 的时间复杂度可以表示为 O(N)，其中 N 是输入的规模。
尽管递归函数的每一层都只执行了一个乘法操作，但由于递归的深度与输入规模相关，最终的时间复杂度是线性的。
总结：递归算法时间复杂度是多次调用的累加。
扩展：
//计算阶乘递归Fac的时间复杂度？ long long Fac(size_t N) { if (0 == N) return 1; for (size_t i = 0; i < N; ++i) { ++count; } return Fac(N - 1) * N; }
阶乘递归函数 Fac 的时间复杂度可以通过递归关系来分析。在这种情况下，递归的深度与输入规模 N 相关，每一层递归都会进行一次乘法操作。让我们分析一下：
第一递归层（N = N）：执行 1 次 Fac(N - 1) * N 乘法 + 执行 N 次 ++count。
第二递归层（N = N-1）：执行 1 次 Fac(N - 2) * N 乘法 + 执行 N-1 次 ++count。
第三递归层（N = N-2）：执行 1 次 Fac(N - 1) * N 乘法 + 执行 N-2 次 ++count。
...
最后一层递归（N = 0）：执行 1 次 Fac(0) * N 乘法 + 执行0次 ++count。
由于上面每次递归执行的乘法只有一次，对于总的操作次数影响较小，可以忽略不记，所以总的操作次数为 N * N /2 次。
因此，阶乘递归函数 Fac 的时间复杂度可以表示为 O(N^2)，其中 N 是输入的规模。
尽管递归函数的每一层都只执行了一个乘法操作，但由于递归的深度与输入规模相关，最终的时间复杂度是线性的。
总结：递归算法时间复杂度是多次调用的累加。
实例八：
// 计算斐波那契递归Fib的时间复杂度？ long long Fib(size_t N) { if (N < 3) return 1; return Fib(N - 1) + Fib(N - 2); }
斐波那契递归函数 Fib 的时间复杂度可以通过递归关系来分析。在这种情况下，递归的深度与输入规模 N 相关，每一层递归都会进行两次递归调用。让我们分析一下：
- 第一层递归（N = N）：执行 2^0 次递归调用。
- 第二层递归（N = N-1）：执行 2^2 次递归调用。
- 第三层递归（N = N-2）：执行 2^3 次递归调用。
- ...
每一层递归调用的次数是指数级别增长的， 总的乘法操作次数为 2^N-1 次。
因此，总的递归调用次数可以近似表示为 2^N 次。
由于每次递归调用都需要一些操作（在这里是两次递归调用），在最坏情况下，每次递归调用的时间开销相对较小。因此，总的时间复杂度仍然可以表示为 O(2^N)。
但是实际上右边会缺少，总的时间复杂度低于等于 O(2^N)。
【解密算法：时间与空间的博弈】（下）：https://developer.aliyun.com/article/1424862
