Как работает heapq.nlargest?

Question

Я смотрел на этот разговор по пикону, 34:30, и оратор говорит, что получение t самые большие элементы списка n элементы могут быть сделаны в O(t + n),

Как это возможно? Я понимаю, что создание кучи будет O(n), а в чем сложность nlargest само по себе, это O(n + t) или же O(t) (и каков фактический алгоритм)?

Answer 1

Динамик не прав в этом случае. Фактическая стоимость O(n * log(t)), Heapify вызывается только на первом t элементы повторяемы. Это O(t), но незначительно, если t намного меньше чем n, Затем все остальные элементы добавляются в эту "маленькую кучу" через heappushpop, один за раз. Это занимает O(log(t)) время на вызов heappushpop, Длина кучи остается t на протяжении. В самом конце сортируется куча, которая стоит O(t * log(t)), но это также незначительно, если t намного меньше чем n,

Весело с теорией;-)

Существуют достаточно простые способы найти самый большой элемент в ожидаемом O(n) время; например, смотрите здесь. Есть худшие способы сделать это в худшем случае O(n) время. Затем, еще раз пройдя через вход, вы можете вывести t элементы>= t-й по величине (с утомительными осложнениями в случае дубликатов). Таким образом, вся работа может быть выполнена в O(n) время.

Но эти способы требуют O(n) память тоже. Python не использует их. Преимущество того, что на самом деле реализовано, заключается в том, что "дополнительная" нагрузка на память в худшем случае O(t)и это может быть очень значительным, когда входной сигнал представляет собой, например, генератор, выдающий очень много значений.

Answer 2

для heapq t наибольшего или t наименьшего временная сложность будет O(nlog(t))

heapq создаст кучу для первых элементов t, а затем будет перебирать оставшиеся элементы, нажимая и вставляя элементы из кучи (сохраняя элементы t в куче.

1. для построения кучи для первых t элементов будет сделано
2. для нажатия и вставки остальных элементов будет выполнено в (n-k)log(t)
3. Общая временная сложность будет nlog(t)

Answer 3

Согласно комментариям в исходном коде heapq :

      # Algorithm notes for nlargest() and nsmallest()
# ==============================================
#
# Make a single pass over the data while keeping the k most extreme values
# in a heap.  Memory consumption is limited to keeping k values in a list.
#

# Theoretical number of comparisons for k smallest of n random inputs:
#
# Step   Comparisons                  Action
# ----   --------------------------   ---------------------------
#  1     1.66 * k                     heapify the first k-inputs
#  2     n - k                        compare remaining elements to top of heap
#  3     k * (1 + lg2(k)) * ln(n/k)   replace the topmost value on the heap
#  4     k * lg2(k) - (k/2)           final sort of the k most extreme values
#
# Combining and simplifying for a rough estimate gives:
#
#        comparisons = n + k * (log(k, 2) * log(n/k) + log(k, 2) + log(n/k))

Answer 4

На самом деле это O (n + t log (n)), потому что heapify принимает O (n), а для каждого элемента наибольшего или наименьшего размера принимает O (log (n)). Таким образом, для t наибольшего / наименьшего требуется t log (n). Следовательно, временная сложность будет O (n + t * log (n))