Я смотрел это выступление на pycon, 34:30, и докладчик говорит, что получение t крупнейших элементов списка из n элементов можно выполнить за O(t + n).
Как это возможно? Насколько я понимаю, создание кучи будет O(n), но какова сложность самого nlargest, это O(n + t) или O(t) (и какой на самом деле алгоритм)?
Подробнее здесь: https://stackoverflow.com/questions/230 ... q-nlargest
