Насколько эффективна функция Python max

Question

Функция max(), которая возвращает максимальный элемент из списка.,,каково его время работы (в Python 3) в терминах Big O нотации ?

Answer 1

Это O (n), так как он должен проверять каждый элемент. Если вам нужна максимальная производительность, вы можете использовать модуль heapq . Однако вы должны отрицать каждое значение , поскольку heapq обеспечивает минимальную кучу. Вставка элемента в кучу - это O (log n).

Answer 2

Зависит от того, как вы его используете. Если вы хотите максимизировать на основе функции «someFunc», потребуется O(len(l)*k), где k - время, которое «someFunc» выполняет для запуска.

maxVal = max(l, key=somefunc)

Но для обычного случая да, он должен просто перебрать список и найти максимум, используя функцию обычного сравнения.

Answer 3

Конечно, это O (n), если вы не используете другую структуру данных, поддерживающую максимум сбора значений из-за некоторого инварианта реализации.