Алгоритм поиска m наибольших элементов списка из списка длиной n элементов
Я примерно понимаю как это можно сделать с помощью quicksort, но там деградировать до квадрата может и реализовывать самому не хочется, есть ли какая-то адекватная реализация на Python'е 3.x? Если знаете, то можно и просто алгоритм.
Буду рад любым подсказкам, спасибо.
Ответы (1 шт):
Непонятно, причем тут "деградировать до квадрата"?
Поиск - это не сортировка. В худшем случае у вас будет O(n*m). m проходов по списку из m элементов, с поиском максимального на каждом проходе и его удаления (отметки) из исходного списка.
При условии, что m<<n - скорость вполне приемлема, особенно при малых m.
Можно еще поиграться с одновременным поиском m максимумов за один проход, но там надо будет дополнительно держать список текущих отобранных. Теоретическая сложность должна бы снизиться, но практическая - либо из-за динамических списков на Python, либо из-за необходимости сдвига массива на С++ - может и не (сильно) улучшиться.