Общая сложность поиска Kth Самый большой элемент в Python

Question

Я решал эту проблему leetcodelink и нашел удивительное решение с использованием модуля heapq, время работы этой функции очень мало. Это ниже программы:

from itertools import islice 
import heapq 

def nlargest(n, iterable): 
    """Find the n largest elements in a dataset. 

    Equivalent to: sorted(iterable, reverse=True)[:n] 
    """ 
    if n < 0: 
     return [] 
    it = iter(iterable) 
    result = list(islice(it, n)) 
    if not result: 
     return result 
    heapq.heapify(result) 
    _heappushpop = heapq.heappushpop 
    for elem in it: 
     _heappushpop(result, elem) 
    result.sort(reverse=True) 
    return result 

print nlargest(5, [10, 122, 2, 3, 3, 4, 5, 5, 10, 12, 23, 18, 17, 15, 100, 101]) 

Этот алгоритм очень умный, и вы также можете сделать визуализировать здесь LINK

Но я с трудом понимая временную сложность всего алгоритма. Вот мой анализ, и, пожалуйста, поправьте меня, если я ошибаюсь!

Время Сложность:

result = list(islice(it, n)) - > O(n) 

heapq.heapify(result) -> O(len(result)) 

for elem in it: 
     _heappushpop(result, elem) -> I am confused at this part 

result.sort(reverse=True) -> O(len(result)*log(len(result))) 

Может кто-нибудь помочь мне понять общую временную сложность алгоритма.

Answer 1

Итак, у вас есть два соответствующих параметра: n (количество возвращаемых товаров) и, скажем, M (количество элементов в наборе данных).

islice(it, n) -- O(n) 
heapify(result) -- O(n), because len(result)=n 
for elem in it: _heappushpop(result, elem) -- performing M-N times an operation of O(logn), because len(result) remains n, i.e. (M-N)*logn 
result.sort(reverse=True) -- O(n*logn) 

Всего:

n + n + (M-n)*logn + n*logn 

Результирующая с O(M*logn). Вы можете легко видеть, что доминирующей частью является цикл heappushpop (предполагая M >> n, в противном случае проблема менее интересна, потому что решение более или менее сводится к сортировке).

---

Стоит отметить, есть л inear-time algorithms для решения этой проблемы, поэтому, если ваш набор данных очень большой, это стоит проверить их.