Учитывая список n сопоставимых элементов (например, числа или строку), оптимальный алгоритм для нахождения упорядоченного элемента i занимает O(n) время.
Выполняет ли Python изначально O(n) статистику по времени для списков, dicts, sets,...?
Ни одна из упомянутых структур данных Python не реализует алгоритм статистики i-го порядка.
Фактически, это может не иметь особого смысла для словарей и множеств, учитывая тот факт, что оба не делают никаких предположений о упорядочении его элементов. Для списков не должно быть сложно реализовать алгоритм выбора который обеспечивает время работы O (n).
Это не родное решение, но вы можете использовать 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.
Если я < n вы можете посмотреть http://docs.python.org/library/heapq.html#heapq.nlargest и http://docs.python.org/library/heapq.html#heapq.nsmallest (не решить вашу проблему, но быстрее, чем сортировать и принимать i-й элемент).