我们如何比较 O(2^n) 和 Θ(2^n) 的时间复杂度？
How can we compare the time complexity of O(2^n) and Θ(2^n)?
一道作业题要比较O(2^n)和Θ(2^n)的时间复杂度
我相信 Θ(2^n) 更好，因为它涵盖了 2^n 的上限和下限，但我不是 sure.Thank 你的时间。
当然，如果有O(2^n)就更好了。因为你可以希望在最坏的情况下它会很糟糕。但这种最坏的情况可能很少发生。因此，平均时间复杂度可能会好得多。例如，您有一种情况发生的概率为 1/2^n，算法针对这种情况运行的计算成本为 2^n，但所有其他情况的算法成本为 1.因此，该算法的复杂度为O(2^n)，但平均复杂度为O(1)。
但是像上面的例子，对于\Theta(2^n)的算法是不会发生的。
但是在 Theta(2^n) 中你会确定平均时间复杂度是 2^n 并且它可能很糟糕。
一道作业题要比较O(2^n)和Θ(2^n)的时间复杂度
我相信 Θ(2^n) 更好，因为它涵盖了 2^n 的上限和下限，但我不是 sure.Thank 你的时间。
当然，如果有O(2^n)就更好了。因为你可以希望在最坏的情况下它会很糟糕。但这种最坏的情况可能很少发生。因此，平均时间复杂度可能会好得多。例如，您有一种情况发生的概率为 1/2^n，算法针对这种情况运行的计算成本为 2^n，但所有其他情况的算法成本为 1.因此，该算法的复杂度为O(2^n)，但平均复杂度为O(1)。
但是像上面的例子，对于\Theta(2^n)的算法是不会发生的。
但是在 Theta(2^n) 中你会确定平均时间复杂度是 2^n 并且它可能很糟糕。