Сортировка строк с использованием Merge Sort

Question

Что будет самой сложной для сортировки n строк, имеющих n символов каждый? Будет ли это всего лишь n раз больше. случай O(n log n) или что-то еще ...?

Answer 1

Как @orangeoctopus, используя стандартный алгоритм ранжирования в коллекции n строки размером n приведут к вычислению O(n^2 * logn).

Однако - обратите внимание, что вы можете сделать это в O(n^2), с изменениями на radix sort.

Самый простой способ сделать это [по-моему] - это

1. построить trie и заполнить его со всеми строками. Ввод каждая строка O(n) и вы делаете это n раз - всего O(n^2)
2. сделать DFS на синтаксическом дереве, каждый раз, когда вы столкнетесь знаком для конца для строки - добавьте его в отсортированную коллекцию. Порядок строк, добавленных таким образом, лексикографически, поэтому ваш список будет отсортирован лексикографически, когда вы закончите.

Легко видеть, что вы не можете сделать это лучше тогда O(n^2), так как только чтение данных является O(n^2), таким образом, это решение является оптимальным с точки зрения большой нотации O сложности времени.

Answer 2

Когда вы говорите о нотации O с двумя вещами различной длины, обычно вы хотите использовать разные переменные, например M и N.

Таким образом, если слияние сортировка O(N log N), где N это число строк ... и сравнение двух строк является O(M) где M весы с длиной строки, то вы останетесь с:

O(N log N) * O(M) 

или

O(M N log N) 

, где M длина строки и N это количество строк. Вы хотите использовать разные ярлыки, потому что они не означают одно и то же.

В странном случае, когда средняя длина строки масштабируется с числом строк, как если бы вы имели матрицу, хранящуюся в строках или что-то вроде этого, можно утверждать, что M = N, и тогда вам придется O(N^2 log N)

Answer 3

Сортировка n элементов с помощью MergeSort требует сравнения O(N LogN). Если время для сравнения двух позиций - O(1), тогда общее время работы будет O(N logN). Однако для сравнения двух строк длины N требуется O(N) времени, поэтому наивная реализация может зависеть от O(N*N logN) времени.

Это кажется расточительным, потому что мы не воспользовались тем фактом, что для сравнения есть только строки N. Мы могли бы как-то препроцитировать строки, чтобы в среднем сравнение занимало меньше времени.

Вот эта идея. Создайте структуру Trie и поместите туда N строк. У trie будет O(N*N) узлов и потребуется O(N*N) времени на сборку. Пройдите дерево и поместите целое «ранжирование» на каждый узел дерева; Если R (N1) < R (N2), то строка, связанная с Node1, предшествует строке, связанной с Node2 в словаре.

Теперь перейдите к Mergesort, выполните сравнения в O(1), просмотрев Trie. Общее время работы будет O(N*N + N*logN) = O(N*N)

Редактировать: Мой ответ очень похож на @amit. Однако я приступаю к объединению, где он продолжает работу с radixsort после этапа построения trie.