max()或min()函数做了多少次比较？

Question

给定一个n数字列表,python中的函数min()或max()函数的比较数是多少？如果这不是最佳,我如何设计执行最少比较的函数？

Answer 1

内置min()并max()迭代列表一次,执行n-1比较(第一个元素与第二个元素,然后前两个元素中的较大元素与第三个元素依此类推).这是O(n)在大O符号.

除非您对列表有所了解(例如以某种方式订购),否则您不能做得更好O(n):任何元素都可以是最小的或最大的,因此需要进行查看.

这里是所使用的两个环的简化和注释的版本min()和max():

it = PyObject_GetIter(v); /* v is the list */
maxitem = NULL; /* the result */
maxval = NULL;  /* the value associated with the result, always
                   the same as maxitem in this simplified version */
while (( item = PyIter_Next(it) )) {
    /* maximum value and item are unset; set them */
    if (maxval == NULL) {
        maxitem = item;
        maxval = item;
    }
    /* maximum value and item are set; update them as necessary */
    else {
        int cmp = PyObject_RichCompareBool(val, maxval, op); /* op is Py_LT or Py_GT */
        if (cmp > 0) {
            maxval = val;
            maxitem = item;
        }
    }
}

(源代码.)

如果需要重复查找和删除集合中最小或最大的元素,并且这会占据整个算法的运行时间,那么查看列表以外的数据结构可能是值得的.

立即想到的一个数据结构是二进制堆.它提供最小(最大)元素的O(n logn)插入和O(n logn)移除.Python在其heapq模块中有一个实现.