I-й порядок статистики в Python

Учитывая список n сопоставимых элементов (например, числа или строку), оптимальный алгоритм для нахождения упорядоченного элемента i занимает O(n) время.

Выполняет ли Python изначально O(n) статистику по времени для списков, dicts, sets,...?

Ответ 1

Ни одна из упомянутых структур данных Python не реализует алгоритм статистики i-го порядка.

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

Ответ 2

Это не родное решение, но вы можете использовать NumPy partition, чтобы найти статистику k-го порядка в списке в O (n).

import numpy as np
x = [2, 4, 0, 3, 1]
k = 2
print('The k-th order statistic is:', np.partition(np.asarray(x), k)[k])

EDIT: это предполагает нулевую индексацию, т.е. "статистика нулевого порядка" выше 0.

Ответ 3

Если я < n вы можете посмотреть http://docs.python.org/library/heapq.html#heapq.nlargest и http://docs.python.org/library/heapq.html#heapq.nsmallest (не решить вашу проблему, но быстрее, чем сортировать и принимать i-й элемент).