Fusion de tableaux triés, quelle est la complexité temporelle optimale?

Question

J'ai m arrays, chaque tableau est de longueur n. Chaque tableau est trié. Je veux créer un seul tableau de longueur m * n, contenant toutes les valeurs des tableaux précédents (y compris les valeurs répétées), triés. Je dois fusionner ces tableaux ..

Je pense que la complexité de temps optimal est m * n * log (m)

Voici le schéma de l'algorithme ..

je crée un tableau de support H lenth m, contenant toutes les valeurs du premier élément de chaque tableau. Puis, je trier cette matrice (m log m) et déplacer la valeur min vers la matrice de sortie. Je remplace ensuite la valeur déplacée par la suivante, à partir de la matrice qui a été prise. En fait, je ne le remplace pas, mais je l'insère dans la bonne position (triée). Cela prend un log m je pense.

Et je le répète pour tous les m * n valeurs ... donc m * n * log m

Ma question .. pouvez-vous penser à un algorithme plus efficace? Si mnlogm est réellement optimal, pouvez-vous au moins penser à un algorithme plus simple et plus élégant?

Answer 1

La complexité est bonne! Cependant, il y a une petite faille dans votre idée d'algorithme: Vous ne pouvez pas insérer un élément dans un tableau trié dans log m. Vous pouvez trouver sa position en utilisant la recherche binaire dans cette complexité, mais vous devrez peut-être déplacer les éléments pour les placer réellement là. Pour résoudre ce problème, vous pouvez utiliser une structure de données de tas à la place!

fusion multi-voies (qui est le nom commun de votre algorithme) est généralement mis en œuvre avec une autre « fusion » structure de données: le tournoi arbre. Vous trouverez une description dans "L'art de la programmation informatique" de Knuth (chapitre sur le tri, iirc). Il a un facteur constant inférieur en théorie et en pratique par rapport aux tas dans ce cas particulier.

Si vous voulez regarder les implémentations, je suis assez sûr que le multi-voies parallèles de fusion dans les extensions parallèles bibliothèque standard GNU C++ est mis en œuvre de cette façon.

Édition: J'ai référencé le mauvais livre, qui est maintenant corrigé.

Answer 2

Le meilleur que vous pouvez faire est O (m * n + d). Semblable au type de comptage: http://en.wikipedia.org/wiki/Counting_sort Si vous connaissez la plage de valeurs possible (d, say), vous pouvez initialiser un tableau de longueur d, puis parcourir chacune des m arrays en ajoutant 1 à chaque 'bin' en d pour chaque valeur correspondante à cette poubelle. Ensuite, dans votre nouveau tableau de longueur m * n pour chaque valeur de d, vous ajoutez cependant autant de comptes que bin a.