好吧，这显然不是一个家庭作业问题，但事情是这样的:气泡排序算法被称为O(n ^ 2)，Ω(n).但是，如果将其时间复杂度绘制为图表(平均情况)，并尝试对其进行下限限制，则更精确的下限将为Ω(n ^ 2).但是从上下文来看，我们看到Ω(n)是正确的.那么为什么下限算法的运行时间不起作用?
Ok so this is not a homework question obviously, but here is the thing: The bubble sort algorithm is said to be O(n^2), Ω(n). However, if we plot its time complexity as a graph (average case), and try to lower bound it, a more accurate lower bound would be Ω(n^2). However contextually we see that Ω(n) is correct. So why does lower bounding the algorithm's runtime does not work?
推荐答案我认为您正在混淆一些概念:
I think you're mixing up concepts:
下限与上限:Ω(f(n))是一个下限，O(f(n))是一个上限.
Lower bound vs upper bound: Ω(f(n)) is a lower bound, and O(f(n)) is an upper bound.
最佳与最坏情况:除非另有说明，否则Ω(f(n))和O(f(n))都是最坏情况下的运行时间，取决于输入大小.
Best vs worst case: Unless otherwise stated, both Ω(f(n)) and O(f(n)) refer to the worst case running time, as a function of the input size.
对于冒泡排序，最差大小为n的案例输入被保证要花费二次时间，因此冒泡排序为O(n 2 )和Ω(n 2 ).
For bubble sort, the worst case input of size n is guaranteed to take quadratic time, so bubble sort is O(n2) and Ω(n2).
原因气泡分类被说成是Ω(n)".是很多人把这个搞砸了.
The reason "bubble sort is said to be Ω(n)" is that a lot of people mess this up.
请记住，Ω(f(n))是在f(n)下渐近界定的函数的 set ，当您看到算法X为Ω(f(n))"，将其读为算法X 的最坏情况运行时间在Ω(f(n))中".
Remember that Ω(f(n)) is the set of functions that are asymptotically bounded underneath by f(n), and when you see "Algorithm X is Ω(f(n))", read it "The worst case running time of Algorithm X is in Ω(f(n))".
(但是请注意，德米特里的答案也是正确的.因为ω是一个下限，所以Ω(1)，Ω(log n)，Ω(n)，Ω(n log n)和Ω(n 2 )全部适用)
(Note however that Dmitry's answer is also also correct. Because omega is a lower bound, Ω(1), Ω(log n), Ω(n), Ω(n log n), and Ω(n2) all apply)