Объединить сортировку в худшем случае для лексикографической сортировки?

Question

Список из n строк длиной n сортируется в лексикографическом порядке с использованием алгоритма сортировки слиянием. Наихудшее время выполнения этого вычисления?

Я получил этот вопрос как домашнее задание. Я знаю сортировку слиянием в O (nlogn) времени. Для лексикографического порядка длины это n раз nlogn? или п ^ 2?

Answer 1

Каждое сравнение алгоритма равно O(n) [сравнение двух строк O(n) наихудший случай - вы можете обнаружить, что оно «больше» только на последнем символе], у вас есть O(nlogn) сравнения в сортировке слиянием.

Таким образом, вы получаете O(nlogn * n) = O(n^2 * logn)

Answer 2

Отношение повторяемости сложности времени составляет

Т (а, б) = 2T (а / 2, б) + О (Ь ^ 2)

Так ясно, что высота дерева будет записана. Таким образом, сложность времени равна O (n ^ 2 * logn).

Answer 3

**answer is O(n^2logn)
  , 
we know Merge sort has recurrence form
T(n) = a T(n/b) + O(n)
in case of merge sort 
it is 
T(n) = 2T(n/2) + O(n) when there are n elements
but here the size of the total is not "n" but "n string of length n"
so a/c to this in every recursion we are breaking the n*n elements in to half
for each recursion as specified by the merge sort algorithm
MERGE-SORT(A,P,R)  ///here A is the array P=1st index=1, R=last index in our case it 
                      is n^2 
if P<R
then Q = lower_ceiling_fun[(P+R)/2]
      MERGE-SORT(A,P,Q)
      MERGE-SORT(A,Q+1,R)
      MERGE (A,P,Q,R)
MERGE(A,P,Q,R) PROCEDURE ON AN N ELEMENT SUBARRAY TAKES TIME O(N)
BUT IN OUR CASE IT IS N*N
SO A/C to this merge sort recurrence equation for this problem becomes
T(N^2)= 2T[(N^2)/2] + O(N^2)
WE CAN PUT K=N^2 ie.. substitute to solve the recurrence
T(K)= 2T(K/2) + O(K)
a/c to master method condition T(N)=A T(N/B) + O(N^d)
                               IF A<=B^d  then T(N)= O(NlogN)
therefore T(K) = O(KlogK)
substituting K=N^2
we get T(N^2)= O(n*nlogn*n)
       ie.. O(2n*nlogn)
         .. O(n*nlogn)

следовательно решено

Answer 4

Но согласно рекуррентному соотношению

T (n) = 2T (n / 2) + O (m * n)

будет T (n) = 2T (n / 2) + O (n ^ 2), когда m = n

Тогда результатом будет O (n ^ 2), а не O (n ^ 2logn).

Поправь меня, если я ошибаюсь.