Merge Trier divisé par 4 - Complexité temporelle du pseudo code

Je dois écrire un pseudo code pour un tri Merge (divisé par 4), et comprendre sa complexité temporelle (Et il doit être dans le temps la complexité de Nlog (n) évidemment).Merge Trier divisé par 4 - Complexité temporelle du pseudo code

ce que j'écrit:

Mergesort4(A){ 
    If (n <= 1) return (A) 
    if (n=0) return(infinity) (Big number) 

    k = (n/4) m=(2n/4) z=(3n/4) 
    Return Merge4(Mergesort4(A[0..k-1]), Mergesort4(A[k..m-1]), 
       Mergesort4(A[m..z-1]), Mergesort4(A[z..n-1), A[0..n-1]) 
    }

Merge4 - Divise B, C, D, matrices de R dans X.

fonction de fusion fusionne 2 tableaux, et la création d'un nouveau tableau pour les éléments triés . (la fonction de fusion est comme dans le 2 sens tri fusion)

Merge4(B,C,D,R,X){ 
      Merge(B,C,E) 
      Merge(D,R,T) 
      Merge(E,T,X) 
}

La complexité du temps est là que je deviens confus.

De toute évidence, T (n) = 4T (n/4) (se divise en 4 problèmes)

Mais je ne sais pas ce qui se passe après la division.

Ma meilleure estimation serait la suivante: T (n) = 4T (n/4) + O (n)

lignes directrices serait apprécié ...

Source

2017-05-13 sheldonzy

L'O (n) provient de l'étape de fusion, qui reste fondamentalement la même. Donc, oui, le terme est O (n) et votre récurrence est la bonne. Vous trouverez que l'arbre de récursivité a des niveaux O (log n) et que O (n) travaille à chaque niveau pour O (n log n) total. – Patrick87

Finalement, la réponse finale:

Mergesort4(A,p,r) 
    If(q < r) 
     q = floor((p+r)/4) 
     Mergesort4(A, p, q) 
     Mergesort4(A, q+1, 2q) 
     Mergesort4(A, 2q+1, 3q) 
     Mergesort4(A, 3q+1, r) 
     Merge(A, p, q, q+1, 2q, 2q+1, 3q, 3q+1, r) 


Merge(A, p, q, q+1, 2q, 2q+1, 3q, 3q+1, r) 

    if(q != 0 && p != 0) 
     Merge(A,p,q,2q) 
    Merge(A,2q+1,3q,r) 
    Merge(A,p,2q+1,r)

Source

2017-05-30 21:28:31 sheldonzy

Merge Trier divisé par 4 - Complexité temporelle du pseudo code

Répondre

Questions connexes