Pourquoi est-k-way merge O(nk^2)?

Question

k-way merge est l'algorithme qui prend en entrée k triés tableaux, chacun de taille n. Il émet un seul tableau trié de tous les éléments.

Il le fait en utilisant la "fusion" de routine centrale de l'algorithme de tri fusion pour fusionner tableau 1 tableau 2 et tableau 3 présente un tableau fusionné, et ainsi de suite jusqu'à ce que tous les k tableaux ont fusionné.

J'avais pensé que cet algorithme est O(kn) parce que l'algorithme parcourt chacun des k tableaux, chacun de longueur n) fois. Pourquoi est-il O(nk^2)?

Answer 1

Car il ne traverse chacun des k tableaux à la fois. Le premier tableau est parcouru k-1 fois, la première fois que la fusion(tableau 1,tableau 2), la seconde fusion(merge(tableau 1, tableau 2), tableau 3) ... et ainsi de suite.

Le résultat est k-1 fusionne avec une taille moyenne de n*(k+1)/2 donnant une complexité de O(n*k^2-1)/2), qui est en O(nk^2).

L'erreur que vous avez fait était oublier que les fusions sont faites en série plutôt qu'en parallèle, de sorte que les tableaux ne sont pas tous de taille n.

Answer 2

En fait, dans le pire des cas,il y aura n comparaisons pour le premier tableau, 2n pour la deuxième, 3n pour la troisième et bientôt jusqu'à (k - 1)n.
Alors maintenant, la complexité devient tout simplement

n + 2n + 3n + 4n + ... + (k - 1)n
= n(1 + 2 + 3 + 4 + ... + (k - 1))
= n((k - 1)*k) / 2
= n(k^2 - k) / 2
= O(nk ^ 2)

:-)

Answer 3

Comment à ce sujet:

Étape 1: Fusionner des tableaux (1 et 2), les tableaux (3 et 4), et ainsi de suite. (k/2 tableau fusionne de 2n, travail total kn).

Étape 2: Fusion array (1,2 et 3,4), les tableaux (5, 6 et 7,8), et ainsi de suite (k/4 fusionne de 4n, travail total kn).

Étape 3: Répéter...

Il y aura log(k) de ces "Étapes", chacun avec kn travail. Donc travail total réalisé = O(k.n.log(k)).

Même si, au contraire, nous avons été à juste trier tous les éléments du tableau, on pourrait encore fusionner tout en O(k.n.log(k.n)) de temps.

Answer 4

Je ne suis pas d'accord avec les autres réponses. Vous n'avez pas à comparer les éléments 1 par 1 à chaque fois. Il vous suffit de maintenir le plus récent K éléments dans un ensemble trié. Vous supprimez la plus petite et la relace par son élément suivant. Ce doit être n.log(k)

Pertinentes de l'article. Avertissement: j'ai participé à l'écriture

Answer 5

k-way merge est l'algorithme qui prend en entrée k triés tableaux, chacun de taille n. Il émet un seul tableau trié de tous les éléments.

J'avais pensé que cet algorithme est O(kn)

On ne peut réfuter que par contradiction. Définir un algorithme de tri pour les m éléments qui utilise un algorithme avec k=m et n=1. Par hypothèse, l'algorithme de tri réussit en O(m) temps. La Contradiction, c'est connu que n'importe quel algorithme de tri a pire des cas au moins O(m log m).