Сортировка строк с использованием Merge Sort - PullRequest
Новая
       18

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

6 голосов
/ 26 февраля 2012

Какая сложность будет для сортировки n строк, содержащих n символов в каждой? Это будет просто n раз его средним кейс O(n log n) или что-то еще ...?

Ответы [ 3 ]

7 голосов
/ 26 февраля 2012

Когда вы говорите о нотации 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)

3 голосов
/ 26 февраля 2012

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

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

Самый простой способ сделать это [на мой взгляд] - это

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

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

0 голосов
/ 26 февраля 2012

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

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

Вот идея. Создайте структуру Trie и поместите туда N строк. Три будет иметь O(N*N) узлов и потребуется O(N*N) времени для сборки. Пройдите по дереву и поставьте целое «ранжирование» для каждого узла в дереве; Если R (N1)

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

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

...