0

Я примерно понимаю как это можно сделать с помощью quicksort, но там деградировать до квадрата может и реализовывать самому не хочется, есть ли какая-то адекватная реализация на Python'е 3.x? Если знаете, то можно и просто алгоритм.

Буду рад любым подсказкам, спасибо.

4
  • sort в Python должен работать за O(n*log(n)) в худшем случае. В чем проблема? Если нужно самому реализовать, то смотрите Timsort и Merge sort 13 сен 2020 в 9:09
  • 1
    Дык если у меня список длины n, а я хочу найти m наибольших элементов, причем m сильно меньше n, то у меня сложность nlogm вместо nlogn, что критично. 13 сен 2020 в 9:10
  • 1
    heapq.nlargest 13 сен 2020 в 9:15
  • Спасибо!....... 13 сен 2020 в 9:17

1 ответ 1

0

Непонятно, причем тут "деградировать до квадрата"?

Поиск - это не сортировка. В худшем случае у вас будет O(n*m). m проходов по списку из m элементов, с поиском максимального на каждом проходе и его удаления (отметки) из исходного списка.

При условии, что m<<n - скорость вполне приемлема, особенно при малых m.

Можно еще поиграться с одновременным поиском m максимумов за один проход, но там надо будет дополнительно держать список текущих отобранных. Теоретическая сложность должна бы снизиться, но практическая - либо из-за динамических списков на Python, либо из-за необходимости сдвига массива на С++ - может и не (сильно) улучшиться.

2
  • Под квадратом я имел в виду жаргон O(mn) 13 сен 2020 в 12:24
  • Тогда причем тут деградировать? Квадратом оно конечно может стать, но только если n=m. А в реальных ситуация - O(mn) << O(nlog(n))
    – passant
    13 сен 2020 в 15:25

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.