入队算法:
ENQUEUE(Q,x)
1.Q[Q.tail]=x
2.if Q.tail==Q.length
3. Q.tail=1
4.else Q.tail=Q.tail+1
时间复杂度为O(1)。
我的问题是为什么它不是 Θ(1)？
最佳答案
它是 O(1) 和 Θ(1)。(除非 x 或 Q.length 有无限位。)
O(1) 表示该算法的时间复杂度至多是一个常量。这是上界。
对于您的情况，假设算法花费时间 t 将 x 插入固定地址 (Q.tail)，并且然后将地址增加 1。很容易看出 t 不会增加，这取决于 n 或 Q 是什么，并且 t 不能是无穷大。所以这个算法的上限是O(1)，因为:
而且，很容易看出，无论n还是Q是什么，t都必须大于一个常数时间才能让机器工作。 t 不能无穷小。所以这个算法的下界是Ω(1)。这意味着该算法的时间复杂度至少是一个常数。
最后，定义如果 T(F(n)) = O(1) 且 T(F(n)) = Ω(1)，则 T(F(n)) = Θ( 1)。 (如果忘记了，请翻阅算法导论的第一章。)
关于algorithm - 为什么以下算法的运行时间是 O(1) 而不是 Θ(1)？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/20686634/