Python中最小值和最大值的大O

Question

Python 中 min 和 max 函数的大 O 是什么？它们是 O(n) 还是 Python 有更好的方法来查找数组的最小值和最大值？如果它们是 O(n) ，那么使用 for 循环来查找所需的值不是更好，还是它们的工作方式与 for 循环相同？

原文由 ᴀʀᴍᴀɴ 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

它是 O(n) 。这是一种通用算法，如果不检查所有算法，一般情况下无法找到最大/最小值。 Python 甚至没有内置的排序集合类型可以使检查易于专门化。

for 循环将具有相同的算法复杂性，但在典型情况下运行速度较慢，因为 min / max （在 CPython 上运行等效）在 C 层循环，避免字节码解释器开销， for 循环会产生。

原文由 ShadowRanger 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

要找到序列的最大值或最小值，您 必须 查看每个元素一次，因此您不能比 O(n) 更好。

当然，Python min 和 max 也有 O(n)： docs 。

您可以使用 for 循环编写自己的 min/max 函数，它具有相同的复杂性，但会更慢，因为它未在 C 中进行优化。

原文由 timgeb 发布，翻译遵循 CC BY-SA 3.0 许可协议