渐近分析问题

Question

我在geeksforgeeks.org上发现了几个我似乎无法理解的问题(#1和#3)。我希望有人能帮我弄清楚答案：

澄清true/valid或false

1. QuickSort的时间复杂度为Θ(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. QuickSort的时间复杂度为O(n^2) -真

3.所有计算机算法的时间复杂度可以写成Ω(1)

这是真的，但我不明白为什么这是真的。一个搜索算法可以有一个Ω(1)的下界，假设我们在第一个元素上找到了我们正在寻找的东西，但是这如何适用于所有的计算机算法，比如最坏情况是O(n^2)的插入排序算法？

链接：http://www.geeksforgeeks.org/analysis-of-algorithms-set-3asymptotic-notations/

Answer 1

QuickSort的时间复杂度是Nlog2( n ^2)-这意味着对于n的每个值，算法产生输出的时间是等于一个函数，它是f(N)=n^2。但我们知道对于快速排序，这不是真的，因为我们知道对于某些输入，快速排序的运行时间可能等于函数Θ(N)=nlogn。因此，我们需要说明“快速排序的最坏情况时间复杂度是Θ(n^2)”是最差的、最好的还是平均的case.It是正确的。

“QuickSort的时间复杂度是O(n^2)”-这意味着对于n的每个输入值，算法的运行时间至多是一个函数f(N)=n^2。这意味着存在一些输入，对于这些输入，算法的运行时间可能小于f(N)=n^2。我们知道快速排序的最佳时间复杂度是g(n)=nlogn .As g(n)< f(n).As这个语句涵盖了所有情况，因此该语句是正确的。

同样，说“quicksort的时间复杂度是nlogn”也是正确的，这意味着算法的运行时间至少是 nlogn，.becauseΩ。

“所有计算机算法的时间复杂度可以写成function.the (1)”-这里1表示常量时间time.which上面的陈述暗示:要执行任何计算机算法，我们需要一个最小常量Ω对于所有计算机算法都是正确的。

Answer 2

对于QuickSort来说，最坏的情况是O(n^2)。但您希望它在O(n log n)时间内运行。因此，算法的运行时间因情况而异，您不能使用theta符号来给出算法的一般运行时间。

当然，任何算法的运行时间的下限都是常数时间(Ω(1))。它不一定要达到这个下限，但是算法应该运行，并且应该至少有一个操作。