从【时间复杂度】到【函数的渐进上界】
函数渐进上界：一般意义上的时间复杂度
给定一个输入大小为 n 的函数：
void algorithm(int n) {int a = 1; // +1a = a + 1; // +1a = a * 2; // +1// 循环 n 次for (int i = 0; i < n; i++) { // +1（每轮都执行 i ++）System.out.println(0); // +1}
}设算法的操作数量是一个关于输入数据大小 n 的函数，记为 T(n)，则以上函数的操作数量为：
T(n) 是一次函数，说明其运行时间的增长趋势是线性的，因此它的时间复杂度是线性阶。
我们将线性阶的时间复杂度记为O(n) ，这个数学符号称为大O记号（big-O notation），表示函数 T(n) 的 渐近上界（asymptotic upper bound）。
时间复杂度分析本质上是计算“操作数量T(n) ”的渐近上界，它具有明确的数学定义。
如下图所示，计算渐近上界就是寻找一个函数 f(n) ，使得当 n 趋向于无穷大时， T(n) 和 f(n) 处于相同的增长级别，仅相差一个常数项 c 的倍数。
最差、最佳、平均时间复杂度
算法的时间效率往往不是固定的，而是与输入数据的分布有关。
假设输入一个长度为 的数组 nums ，其中 nums 由从 至 的数字组成，每个数字只出现一次；但元素顺序是随机打乱的，任务目标是返回元素的索引。我们可以得出以下结论。
- 当
nums = [?, ?, ..., 1]，即当末尾元素是 1 时，需要完整遍历数组，达到最差时间复杂度O(n) 。
- 当
nums = [1, ?, ?, ...]，即当首个元素为时，无论数组多长都不需要继续遍历，达到最佳时间复杂度(1) 。
“最差时间复杂度”对应函数渐近上界，使用大O记号表示。
相应地，“最佳时间复杂度”对应函数渐近下界，用 记号表示：
值得说明的是，我们在实际中很少使用最佳时间复杂度，因为通常只有在很小概率下才能达到，可能会带来一定的误导性。而最差时间复杂度更为实用，因为它给出了一个效率安全值，让我们可以放心地使用算法。
从上述示例可以看出，最差时间复杂度和最佳时间复杂度只出现于“特殊的数据分布”，这些情况的出现概率可能很小，并不能真实地反映算法运行效率。相比之下，平均时间复杂度可以体现算法在随机输入数据下的运行效率，用记号来表示。
对于部分算法，我们可以简单地推算出随机数据分布下的平均情况。比如上述示例，由于输入数组是被打乱的，因此元素 1 出现在任意索引的概率都是相等的，那么算法的平均循环次数就是数组长度的一半 ，平均时间复杂度为(n/2)=
(n)。
但对于较为复杂的算法，计算平均时间复杂度往往比较困难，因为很难分析出在数据分布下的整体数学期望。在这种情况下，我们通常使用最差时间复杂度作为算法效率的评判标准。
总结：
- 最差时间复杂度用O表示（读作：big O）
- 最佳时间复杂度用
- 平均时间复杂度用
表示
声明：本文内容来自于开源项目 Hello 算法，更多资源请移步学习。