pro.algorithms
Вопрос, есть задача merge k sorted lists. Можно ли ее
решить быстрее nklogk? Когда-то давно мне парень из джинотеги рассказывал быстрое решение, но не могу к нему прийти. И у меня уже ощущение, что мы другую задачу обсуждали
4 ответов
каждый из списков - размером n?
Даже интересно, что за парень из джинотеги.
Если бы было решение быстрее, то это означает, что на этой основе можно сделать сортировку за быстрее чем nlog(n) -> Отсортировать оригинаньный массив размера N в sqrt(N) массивов(листов) размера sqrt(N) - за N * log(sqrt(N)), + сложность твоего алгоритма, который N * log(sqrt(N)), если бы их сумма не сходилась к N * log(N), то это означало, что его можно было бы запускать рекурсивно и создать сортировку быстрее чем за n*log(n) Верно же?
https://www.google.com/amp/s/www.geeksforgeeks.org/merge-k-sorted-linked-lists/amp/
Похожие вопросы
Обсуждают сегодня