tri par fusion complexité

Question

Nous savons que la fusion a en quelque sorte le temps complexité O (nlogn) pour l'algorithme ci-dessous:

void mergesort(n elements) { 
mergesort(left half); ------------ (1) 
mergesort(right half); ------------(2) 
merge(left half, right half); 

Quelle sera la complexité de temps pour les implémentations suivantes?

(1) 
void mergesort(n elements) { 
    mergesort(first quarter); ------------ (1) 
    mergesort(remaining three quarters); ------------(2) 
    merge(first quarter, remaining three quarters); 

(2) 
void mergesort(n elements) { 
    mergesort(first quarter); ------------ (1) 
    mergesort(second quarter); ------------(2) 
    mergesort(third quarter); ------------ (3) 
    mergesort(fourth quarter); ------------(4) 
    merge(first quarter, second quarter,third quarter, fourth quarter); 

Veuillez expliquer comment vous trouvez les complexités.

Answer 1

Tous les trois des algorithmes que vous avez posté sont O (n log n), juste avec constantes légèrement différentes. L'idée de base est qu'il prend des passes log (n), et à chaque passe, vous examinez n éléments. Peu importe la taille de vos partitions et, en fait, vous pouvez avoir des partitions de taille variable. Cela fonctionne toujours à O (n log n). La différence d'exécution sera la méthode merge. La fusion de listes triées est une opération O (n log k), où n est le nombre total d'éléments à fusionner et k le nombre de listes. Donc, la fusion de deux listes est n * log(2), ce qui revient à n (parce que log2(2) == 1). Voir ma réponse à How to sort K sorted arrays, with MERGE SORT pour plus d'informations.

Answer 2

Toujours O (n log n) car la base de log 4 de n = log n/log 4, qui finit par être constante.

[EDIT]

La relation recurence de l'algorithme de tri de fusion avec split k est la suivante. Je suppose que la fusion k tableaux triés avec un total de n éléments coût n log2 (k), log2 représentant la base du journal 2.

T(1) = 0 
T(n) = n log2(k) + k T(n/k) 

je pouvais résoudre la relation recurence à:

T(n) = n log2(n) 

quel que soit la valeur de k.

Answer 3

Notez que ce n'est pas une réponse exacte à votre question mais un indice.

Nous devons d'abord comprendre comment la complexité temporelle du tri par fusion par défaut est n (log n).

Si nous avons 8 éléments et par défaut l'approche de mergesort, si nous continuons à les diviser en deux à chaque fois jusqu'à atteindre un groupe contenant un seul élément, cela nous prendra 3 pas. Cela signifie que mergersort est appelé 3 fois sur N éléments. C'est pourquoi la complexité temporelle est 3 * 8 ie (log N) * N

Si vous changez la partition par défaut de la moitié à autre part, vous devrez compter, combien d'étapes il pour vous pour atteindre le groupe de 1 éléments.

Notez également que cette réponse vise uniquement à expliquer comment la complexité est calculée. Big O complexité de toute l'approche de la partition est même et même 2 partition si mis en œuvre de manière efficace aura complexité exacte de N (logN)