Сколько сравнений выполняет функция max () или min ()? - PullRequest
Новая
       9

Сколько сравнений выполняет функция max () или min ()?

0 голосов
/ 07 октября 2018

Учитывая список n чисел, какое число сравнений выполняет функция min() или max() в python?Если это не оптимально, как я могу разработать функцию, которая выполняет наименьшее сравнение?

1 Ответ

0 голосов
/ 07 октября 2018

Встроенные min() и max() выполняют итерацию по списку один раз, выполняя n-1 сравнения (первый элемент со вторым, затем больший из первых двух с третьим и т. Д.).Это O(n) в big-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 модуле .

...