マージは、辞書順ソートの最悪の場合の実行時間をソートしますか？

Question

各長さnのn個の文字列のリストは、マージソートアルゴリズムを使用して辞書順にソートされます。この計算の最悪の場合の実行時間は？

私は宿題としてこの質問を受けました。私はO（nlogn）時間でソートソートを行うことを知っています。長さの辞書順はn回n回ですか？またはn^2？

Answer 1

アルゴリズムの各比較は、[2つの文字列を比較することO(n)最悪のケースである - あなただけの最後の文字の「大きな」であるかを検出可能性がある] O(n)である、あなたはマージソートでO(nlogn)比較を持っています。

したがってあなたはO(nlogn * n) = O(n^2 * logn)

Answer 2

を取得しかし、漸化

T（N）= 2T（N/2）+ O（M×n個）

に従ってN（ Tだろうm = nのとき2T（n/2）+ O（n^2）となる。

結果はO（n^2）であり、O（n^2logn）ではない。

私が間違っている場合は私を修正してください。

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（A、B）= 2T（/ 2、B）+ O（B^2）

で解決しました

ツリーの高さは明らかにlognになります。 したがって、時間の複雑さはO（n^2 * logn）です。