O(1) 和 O(log n)，它们是一回事吗？
O(1) and O(log n), are they same thing?
有个问题问从最小堆中取出一个最小元素是否是o(logn)时间，我认为它是错误的，因为它需要常数时间，因为最小元素在顶部。但答案是正确的，导师的解释是常数时间也是O(logn)，这是一个措辞问题。我很困惑。所以在实践中，我们是否认为常数时间是 O(logn) 的运行时间？
原来O记法只是问题的上界。恒定时间可以用任何 O 表示法表示，因为上界没有限制，甚至可能一直到 n!。大 O 符号不是 theta。
的确，任何复杂度为 O(1) 的东西都是复杂度 O(log n)。然而，并不是所有的 O(log n) 都是 O(1)。 O 是上限，因此您始终可以使用增长更快的函数。
可以这样想：
- 米老鼠是一只老鼠
- 所有老鼠都是哺乳动物
- 因此，米老鼠是哺乳动物
- ...但是 "mice" 和 "mammals" 不是同义词
从最小堆中取出最小元素是一个 O(log n) 操作，因为它包含两个步骤：
- 获取最小项，正如您指出的那样，它的复杂度为 O(1)，因为已知它位于堆的顶部。
- 正在删除最少的项目。这是 O(log n)，因为它涉及将最后一项从堆移到根，然后向下筛选以重新调整堆。
如果你只是想得到最小项而不移除它，那么这个操作确实是O(1)。但是任何时候你想修改堆（并且删除第一项当然符合条件），这是一个 O(log n) 操作。
挑剔者注意：
我理解插入到最小堆中的论点，平均 ，一个 O(1) 操作。尽管在某些情况下这可能是正确的，但最坏的情况仍然是 O(log n)。 （尝试以相反的顺序将值插入堆。每次插入都是 O(log n)。）
有个问题问从最小堆中取出一个最小元素是否是o(logn)时间，我认为它是错误的，因为它需要常数时间，因为最小元素在顶部。但答案是正确的，导师的解释是常数时间也是O(logn)，这是一个措辞问题。我很困惑。所以在实践中，我们是否认为常数时间是 O(logn) 的运行时间？
原来O记法只是问题的上界。恒定时间可以用任何 O 表示法表示，因为上界没有限制，甚至可能一直到 n!。大 O 符号不是 theta。
的确，任何复杂度为 O(1) 的东西都是复杂度 O(log n)。然而，并不是所有的 O(log n) 都是 O(1)。 O 是上限，因此您始终可以使用增长更快的函数。
可以这样想：
- 米老鼠是一只老鼠
- 所有老鼠都是哺乳动物
- 因此，米老鼠是哺乳动物
- ...但是 "mice" 和 "mammals" 不是同义词
从最小堆中取出最小元素是一个 O(log n) 操作，因为它包含两个步骤：
- 获取最小项，正如您指出的那样，它的复杂度为 O(1)，因为已知它位于堆的顶部。
- 正在删除最少的项目。这是 O(log n)，因为它涉及将最后一项从堆移到根，然后向下筛选以重新调整堆。
如果你只是想得到最小项而不移除它，那么这个操作确实是O(1)。但是任何时候你想修改堆（并且删除第一项当然符合条件），这是一个 O(log n) 操作。
挑剔者注意： 我理解插入到最小堆中的论点，平均 ，一个 O(1) 操作。尽管在某些情况下这可能是正确的，但最坏的情况仍然是 O(log n)。 （尝试以相反的顺序将值插入堆。每次插入都是 O(log n)。）