我在 geeksforgeeks.org 上发现了一些我似乎无法理解的问题（#1 和 #3）。我希望有人可以为我澄清答案：
澄清是真/有效还是假
1.快速排序的时间复杂度是Θ(n^2)
我的回答是对的，但它是错的，为什么？如果快速排序的时间复杂度为 O(n^2) 并且我们知道 Θ(g(n))={f(n) 其中 c1*g(n) <= f(n) <=c2*g(n ) 并且 n >= n0} 那么这是否证明它是正确的，因为 c2*g(n) 作为上限可以等于 f(n)？
2.快速排序的时间复杂度是 O(n^2) - true
3.所有计算机算法的时间复杂度可以写成Ω(1)
这是真的，但我不明白为什么这是真的。假设我们在第一个元素上找到了我们正在寻找的东西，搜索算法可以具有 Ω(1) 的下限，但这对于所有计算机算法（例如最坏情况为 O(n^2) 的插入排序算法来说如何成立)?
链接： http ://www.geeksforgeeks.org/analysis-of-algorithms-set-3asymptotic-notations/
QuickSort 的时间复杂度是 Θ(n^2)----这意味着对于每个 n 值，算法产生输出所用的时间等于函数 f(n)=n^2。但是我们知道这不适用于快速排序，因为我们知道对于某些输入，快速排序的运行时间可能等于 g(n)=nlogn 的函数。所以我们需要指定它是最坏、最好还是平均情况。说“快速排序的最坏情况时间复杂度是 Θ(n^2)”是正确的。
“快速排序的时间复杂度是 O(n^2)”——这意味着对于每个输入值 n，算法的运行时间最多是一个函数，即 f(n)=n^2。这意味着存在一些输入，算法的运行时间可能小于 f(n)=n^2。我们知道快速排序的最佳情况时间复杂度是 g(n)=nlogn 和 g(n)< f(n) .由于该陈述涵盖所有情况，因此该陈述是正确的。
同样，“快速排序的时间复杂度为 Ω(nlogn)”是正确的。因为这意味着算法的运行时间至少为nlogn，并且 n^2>nlogn。
“所有计算机算法的时间复杂度都可以写成 Ω(1)”---这里 1 代表常数时间函数。上面的陈述意味着：要执行任何计算机算法，我们需要一个最小常数时间。这对于所有计算机算法都是正确的.
快速排序的最坏情况是O(n^2). 但是您希望它及时运行O(n log n)。因此，算法的运行时间因情况而异，您不能使用 theta 符号来给出算法的一般运行时间。
当然，任何算法的运行时间下限都是常数时间（Ω(1)）。虽然它不必达到这个下限，但应该运行算法，并且应该至少有一个操作。