Python中min和max的大O.

Question

什么是的大O min和max功能在Python？他们O(n)或者Python有更好的方法来查找数组的最小值和最大值吗？如果它们是O(n),使用for循环来找到所需的值或者它们的工作方式与for循环相同是不是更好？

Answer 1

是的O(n).这是一种通用算法,如果不检查所有这些,就无法在一般情况下找到最大值/最小值.Python甚至没有内置的有序集合类型,这使得检查很容易专门化.

Answer 2

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

当然，Pythonmin也max有 O(n)：docs。

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