Temps d'exécution du tri de fusion dans le pire des cas pour le tri lexicographique ?

Question

Une liste de n chaînes de caractères, chacune de longueur n, est triée dans l'ordre lexicographique à l'aide de l'algorithme de tri par fusion. Le temps d'exécution de ce calcul dans le pire des cas est ?

J'ai reçu cette question en guise de devoir. Je sais que le tri par fusion se fait en O(nlogn) temps. Pour l'ordre lexicographique pour une longueur de est ce que c'est n fois nlogn ? ou n^2 ?

Answer 1

Chaque comparaison de l'algorithme est O(n) [la comparaison de deux chaînes de caractères est O(n) dans le pire des cas, vous pourriez détecter lequel est le plus grand uniquement sur le dernier caractère], Vous avez O(nlogn) des comparaisons en mergesort.

Vous obtenez ainsi O(nlogn * n) = O(n^2 * logn)

Answer 2

Mais selon la relation de récurrence

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

Sera T(n) = 2T(n/2) + O(n^2) lorsque m = n

Le résultat sera alors O(n^2) et non O(n^2logn).

Corrigez-moi si je me trompe.

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)

donc résolu

Answer 4

La relation de récurrence de complexité temporelle est

T(a,b)=2T(a/2,b)+O(b^2)

Il est donc évident que la hauteur de l'arbre sera logn. La complexité temporelle est donc O(n^2*logn).