algorithm - 我们如何比较 O(2^n) 和 Θ(2^n) 的时间复杂度？

Question

对于作业问题，我必须比较 O(2^n) 和 Θ(2^n) 的时间复杂度。

我相信 Θ(2^n) 更好，因为它涵盖了 2^n 的上限和下限，但我不确定。谢谢您的宝贵时间。

标签： algorithmcomparisonbig-ocomplexity-theory

Answer 1

当然，如果你有O(2^n)会更好。因为你可以希望在最坏的情况下它会很糟糕。但最坏的情况可能很少发生。因此，平均时间复杂度可能要好得多。例如，您有一种情况发生的概率为1/2^n，并且算法在这种情况下以2^n计算成本运行，但对于所有其他情况，算法的成本为1. 因此，该算法的复杂度为O(2^n)，但平均复杂度为O(1)。

然而，就像上面的例子一样，算法不会发生\Theta(2^n). 但是Theta(2^n)您会确定平均时间复杂度是2^n并且可能很糟糕。