runtime - O(1) 和 O(log n)，它们是一回事吗？

Question

有一个问题询问从最小堆中获取最小元素是否是 o(logn) 时间，我认为这是错误的，因为它需要恒定时间，因为最小元素在顶部。但答案是正确的，导师的解释是常数时间也是 O(logn)，这是一个措辞问题。我很困惑。所以在实践中，我们是否认为常数时间是 O(logn) 的运行时间？

Answer 1

确实，任何 O(1) 都是 O(log n)。然而，并不是所有的 O(log n) 都是 O(1)。O 是一个上限，因此您始终可以使用增长更快的函数。

可以这样想：

• 米老鼠是一只老鼠
• 所有的老鼠都是哺乳动物
• 因此，米老鼠是哺乳动物
• ...但是“老鼠”和“哺乳动物”不是同义词

Answer 2

从最小堆中取出最小元素是一个 O(log n) 操作，因为它包含两个步骤：

1. 正如您所指出的，获取最小项目是 O(1)，因为它已知位于堆的顶部。
2. 删除最小项目。这是 O(log n)，因为它涉及将最后一项从堆移动到根，然后将其向下筛选以重新调整堆。

如果你只是想得到最小项而不删除它，那么操作确实是 O(1)。但是任何时候你想修改堆（并且删除第一个项目肯定是合格的），这是一个 O(log n) 操作。

吹毛求疵的人注意：我理解插入最小堆平均是 O(1) 操作的论点。虽然在某些情况下可能是这样，但最坏的情况仍然是 O(log n)。（尝试以相反的顺序将值插入堆中。每次插入都是 O(log n)。）

Answer 3

事实证明，O 表示法只是问题的上限。常数时间可以用任何 O 符号表示，因为上限没有限制，甚至可能一直到 n!。大 O 表示法不是 theta。