渐近下界不起作用。为什么？
Asymptotic lower bounding does not work. Why?
好吧，这显然不是作业问题，但问题是：
据说冒泡排序算法是 O(n^2), Ω(n)。
但是，如果我们将其时间复杂度绘制为图形（平均情况），并尝试对其下限，则更准确的下限将是 Ω(n^2)。然而，在上下文中我们看到 Ω(n) 是正确的。那么为什么下界算法的运行时不起作用？
Ω(n) 根据定义是下限，不必很紧。它只是保证算法的效果不比线性好。
Ω(1), Ω(log(n)) 也是冒泡排序执行时间的有效下限。信息量不大，但仍然有效。
我认为你混淆了概念：
下限与上限：Ω(f(n))是下限，O(f(n))是上限。
最佳与最坏情况：除非另有说明，Ω(f(n)) 和 O(f(n)) 均指最坏情况 运行 时间，作为函数输入大小。
对于冒泡排序，最差 情况输入的大小 n 保证 需要二次时间，所以冒泡排序是 O(n 2) 和 Ω(n2).
“冒泡排序据说是 Ω(n)”的原因是 很多 的人搞砸了。
请记住，Ω(f(n)) 是函数的 集合，它们在 f(n) 下渐进有界，当您看到“算法 X 是 Ω( f(n))”，阅读它“算法 X 的最坏情况 运行 时间在 Ω(f(n))”。
（但请注意，Dmitry 的答案也是正确的。因为 omega 是下限，Ω(1)、Ω(log n)、Ω(n)、Ω(n log n) 和 Ω(n 2) 全部适用)
下列说法都是正确的：
- 对于每个数字 n，冒泡排序永远不会在长度为 n 的列表上执行超过 n(n-1)/2 次比较和 n(n-1)/2 次交换
- 对于每个数字 n，存在一个长度为 n 的列表，冒泡排序恰好在该列表上执行 n(n-1)/2 次比较和 n(n-1)/2 次交换（示例：反向排序的列表顺序)
- 对于每个数字 n，冒泡排序从不对长度为 n 的列表执行少于 (n-1) 次比较
- 对于每个数字 n，存在一个长度为 n 的列表，冒泡排序在其上执行恰好 (n-1) 次比较和 0 次交换（示例：排序列表）
- 对于每一个数n，如果我们将列表[1,2,...,n]随机均匀打乱，那么冒泡排序的预期交换次数为n(n-1)/ 4（解释：this answer on CS.stackexchange）
结论：如果我们忘记乘法常数，worst-case运行次是n^2，best-case运行次冒泡排序为n次，平均运行次为n^2.
请注意，“平均 运行 时间”总是有点模棱两可。为了消除歧义，我在最后一个要点中做了不同的陈述。如果您的随机列表遵循不同的概率分布，那么您将得到不同的结果。特别是，冒泡排序在具有大量重复元素的列表上需要更少的交换（可能更少的比较）。但是，如果您不关心确切的乘法常数，那么生成“随机列表”的大多数“合理”方法将导致 n^2 的预期复杂度。
现在，您的问题可能会变成：为什么冒泡排序的预期 运行 时间与它的 worst-case 运行 时间如此接近，而与它的时间相差如此之远？它的 best-case 运行 时间？
这个问题的答案是：绝大部分排列是“合理洗牌”的，只有少数排列是“差不多排序”的。换句话说，如果你随机打乱一个列表，那么结果将“看起来是随机的”。如果你洗一副牌，你不小心把牌排序的概率很低。
题目也有点骗人：worst-case比较的次数是n^2/2；预期的比较次数为 n^2/4； best-case 次比较是 n-1。所以实际上，预期的比较次数几乎恰好是最坏情况和最好情况之间的half-way。
CS.stackexchange上的回答也是很好的解释：在列表中的所有元素对中，我们希望一半对是相对顺序，一半对是相反的相对顺序.所以预期的运行时间恰好是worst-case运行时间的一半。
好吧，这显然不是作业问题，但问题是： 据说冒泡排序算法是 O(n^2), Ω(n)。 但是，如果我们将其时间复杂度绘制为图形（平均情况），并尝试对其下限，则更准确的下限将是 Ω(n^2)。然而，在上下文中我们看到 Ω(n) 是正确的。那么为什么下界算法的运行时不起作用？
Ω(n) 根据定义是下限，不必很紧。它只是保证算法的效果不比线性好。
Ω(1), Ω(log(n)) 也是冒泡排序执行时间的有效下限。信息量不大，但仍然有效。
我认为你混淆了概念：
下限与上限：Ω(f(n))是下限，O(f(n))是上限。
最佳与最坏情况：除非另有说明，Ω(f(n)) 和 O(f(n)) 均指最坏情况 运行 时间，作为函数输入大小。
对于冒泡排序，最差 情况输入的大小 n 保证 需要二次时间，所以冒泡排序是 O(n 2) 和 Ω(n2).
“冒泡排序据说是 Ω(n)”的原因是 很多 的人搞砸了。
请记住，Ω(f(n)) 是函数的 集合，它们在 f(n) 下渐进有界，当您看到“算法 X 是 Ω( f(n))”，阅读它“算法 X 的最坏情况 运行 时间在 Ω(f(n))”。
（但请注意，Dmitry 的答案也是正确的。因为 omega 是下限，Ω(1)、Ω(log n)、Ω(n)、Ω(n log n) 和 Ω(n 2) 全部适用)
下列说法都是正确的：
- 对于每个数字 n，冒泡排序永远不会在长度为 n 的列表上执行超过 n(n-1)/2 次比较和 n(n-1)/2 次交换
- 对于每个数字 n，存在一个长度为 n 的列表，冒泡排序恰好在该列表上执行 n(n-1)/2 次比较和 n(n-1)/2 次交换（示例：反向排序的列表顺序)
- 对于每个数字 n，冒泡排序从不对长度为 n 的列表执行少于 (n-1) 次比较
- 对于每个数字 n，存在一个长度为 n 的列表，冒泡排序在其上执行恰好 (n-1) 次比较和 0 次交换（示例：排序列表）
- 对于每一个数n，如果我们将列表[1,2,...,n]随机均匀打乱，那么冒泡排序的预期交换次数为n(n-1)/ 4（解释：this answer on CS.stackexchange）
结论：如果我们忘记乘法常数，worst-case运行次是n^2，best-case运行次冒泡排序为n次，平均运行次为n^2.
请注意，“平均 运行 时间”总是有点模棱两可。为了消除歧义，我在最后一个要点中做了不同的陈述。如果您的随机列表遵循不同的概率分布，那么您将得到不同的结果。特别是，冒泡排序在具有大量重复元素的列表上需要更少的交换（可能更少的比较）。但是，如果您不关心确切的乘法常数，那么生成“随机列表”的大多数“合理”方法将导致 n^2 的预期复杂度。
现在，您的问题可能会变成：为什么冒泡排序的预期 运行 时间与它的 worst-case 运行 时间如此接近，而与它的时间相差如此之远？它的 best-case 运行 时间？
这个问题的答案是：绝大部分排列是“合理洗牌”的，只有少数排列是“差不多排序”的。换句话说，如果你随机打乱一个列表，那么结果将“看起来是随机的”。如果你洗一副牌，你不小心把牌排序的概率很低。
题目也有点骗人：worst-case比较的次数是n^2/2；预期的比较次数为 n^2/4； best-case 次比较是 n-1。所以实际上，预期的比较次数几乎恰好是最坏情况和最好情况之间的half-way。
CS.stackexchange上的回答也是很好的解释：在列表中的所有元素对中，我们希望一半对是相对顺序，一半对是相反的相对顺序.所以预期的运行时间恰好是worst-case运行时间的一半。