Le temps de la complexité de la fusion de deux tableaux triés de taille n et m
Je me demandais juste quel est le temps complexty de la fusion de deux tableaux triés de taille n et m, étant donné que n est toujours plus grande que m.
Je pensais de l'aide de fusion de tri, qui, je suppose, dans ce cas, consommer de O(log n+m).
Je ne suis pas vraiment bonne avec des gros-oh et d'autres choses. Merci de me suggérer la complexité du temps pour ce problème, et laissez-moi savoir si il y a un même optimisée de la manière de résoudre le problème.
Merci d'avance.
Devrait être en été le temps maintenant, mais des devoirs?
OriginalL'auteur dnawab | 2012-06-14
Vous devez vous connecter pour publier un commentaire.
Attention! Cette réponse contient une erreur
Un algorithme plus efficace existe et il est présenté dans une autre réponse.
La complexité est O(m log n).
Laissez le long de la matrice sera appelé
a
et le tableau short êtreb
alors l'algorithme décrit peut être écrite commeIl y a m itérations de la boucle. Chaque insertion dans un tableau trié est un O(log n) opérations. Par conséquent, la complexité est O (m log n).
Depuis
b
est triée dans l'algorithme ci-dessus peut être rendue plus efficaceCela peut-il donner une meilleure complexité asymptotique? Pas vraiment.
Supposons que les éléments de
b
sont répartis de façon uniforme le long dea
. Ensuite, chaque insertion prendraO(log (n/m))
et la complexité globale seraO(m log(n/m) )
. Si il existe une constantek>1
qui ne dépend pas den
oum
tels quen > k * m
puisO(log(n/m)) = O(log(n))
et nous obtenons la même complexité asymptotique comme ci-dessus.Btw désolé pour le downvote - a l'origine, je pensais que votre réponse n'était tout simplement inefficace, mais en sont venus à comprendre qu'il ne l'est pas. DONC, ne me laisse pas upvote encore bien moins que la réponse est édité; peut-être que vous pourriez le faire?
"Par conséquent, la complexité est O (m log n)." L'Insertion dans un tableau de n éléments est lui-même un O(n), parce que chaque élément doit être déplacé vers la droite. Serait alors en O(m * log n) dans la phrase citée ci-dessus en fait être O (mn log n)?
OriginalL'auteur Dmitri Chubarov
Le temps de la fusion de deux listes triées n'est certainement pas O(m log n). Il est O(n+m).
Le code ressemble à ceci:
Maintenant, si nous n'avons pas assez de mémoire pour allouer c ce qui peut être modifié pour toujours être en O(n+m), comme la plupart du matériel (mémoire vive (RAM) et les disques durs par exemple) permettent de bloquer les opérations. lorsque nous avons besoin d'insérer un élément unique dans le milieu du tableau, il est une seule opération pour déplacer l'extrémité de queue de la bloquer plus d'un pour faire de la place. Si vous avez été sur le matériel qui ne permet pas cela, alors vous feriez peut-être avez-O(n) pour chaque insertion, qui serait alors en O(n+mn) de la complexité. Depuis, nous avons seulement besoin d'insérer des éléments de la petite taille de tableau dans la plus grande jamais nous avons besoin de changement de pièces de l'ensemble plus grand lorsque l'élément que l'on est déjà à la bonne place. Par conséquent, le n reste le même et la complexité de la m bits est augmenté. C'est le pire des cas illustré lors de la tous les de la matrice b de longueur m est correctement placé devant un tableau de longueur n.
Ne devrions-nous pas considérer le cas: a[i] = b[j]?
supposons qu'ils sont numéro unique
OriginalL'auteur Matt Vang