le temps de la complexité de la fusion de tri

pourquoi la complexité du temps de meilleur des cas, de haut en bas de fusion de tri est en O(nlogn)?
je pense que le meilleur des cas, de haut en bas de fusion de tri est de 1, seulement le besoin de comparer 1 fois.
comment à propos de la complexité du temps de du bas jusqu'à la fusion de tri dans le pire des cas, dans le meilleur des cas et de la moyenne des cas.

Une autre question est pourquoi chaque itération prend exactement O(n)? peut-on aider?

  • O(1)? Peut-être O(n) par le prétraitement et la vérification le tableau est déjà trié.
  • "meilleur des cas" signifie, "le meilleur des cas étant donné que la taille de l'entrée est n", pas de "meilleur des cas, en supposant qu'il y a seulement 2 éléments à trier".
  • Décrivez votre algorithme que vous pensez qu'il O(1) et nous pouvons sans doute vous dire où il est mal...
  • À moins que l'algorithme s'avère être une sorte de seau de tri, il n'y a pas "probablement" 🙂
  • en.wikipedia.org/wiki/Merge_sort pour tous les renseignements que vous voudrez probablement (incroyable ce que google va faire pour vous).
InformationsquelleAutor J.L | 2012-10-12
  1. 5

    pourquoi la complexité du temps de meilleur des cas, de haut en bas de fusion de tri est en
    O(nlogn)?

    Parce qu'à chaque itération, vous diviser le tableau en deux sous-listes, et appeler récursivement l'algorithme. Dans le meilleur des cas vous diviser exactement à la moitié, et ainsi de vous réduire le problème (de chaque appel récursif) à la moitié du problème. Vous avez besoin log_2(n) itérations, et à chaque itération prend exactement O(n) (chaque itération est sur toutes les sous-listes, la taille totale est de toujours n), donc au total O(nlogn).

    Cependant, avec un simple prétraitement pour vérifier si la liste est déjà triée - elle peut être réduite à O(n).

    Depuis de vérifier si une liste est triée est lui-même O(n) - il ne peut pas être fait dans O(1). Notez que le "meilleur des cas" est le "meilleur des cas" pour n, et pas une taille spécifique.

    comment à propos de la complexité du temps de du bas jusqu'à la fusion de tri dans le pire des cas,
    dans le meilleur des cas et de la moyenne des cas.

    La même approche peut vous donner O(n) dans le meilleur des cas de bas en haut (simple pré-traitement). Le pire des cas et dans le meilleur des cas des bas jusqu'à la fusion de tri est O(nlogn) - car dans cette approche, la liste est toujours divisée en 2 parts égales de longueur (à la différence 1) les listes.

    • pourquoi les itérations doit être log_2(n)? est-il une formule pour cela? et une autre question est au sujet de l'arbre binaire, pourquoi la longueur de l'arbre binaire est log(n).
    • au niveau le plus profond de la récursivité, vous avez 1 élément. Le 2ème niveau, vous disposez de 2. Le 3ème niveau, vous avez 4, le 4ème niveau, vous avez 8, .... à la i-ième niveau, vous avez 2^(i-1) de l'élément. Donc, nous sommes à la recherche pour i tels que 2^(i-1) = n. depuis 2^logn == n, nous concluons i = logn+1 - de sorte que le nombre total d'itérations est O(logn) La même pour les arbres binaires
    • ce que tu veux dire par le fait d'avoir 1 élément 2 éléments? voulez-vous dire qu'au début, il y a une liste de tableau, d'autre part, il est séparé en deux parties, de sorte que jusqu'à présent..
    • C'est de cette façon de fusion tri fonctionne, au niveau le plus profond (l'arrêt de la clause de), vous disposez d'un élément. Au niveau de l'avant de 2 éléments, ... à Chaque niveau de la récurrence est de travailler sur certains sous-liste de l'original, cette sous-liste est de la longueur que j'ai décrit (1,2,4,...2^(i-1))
    • merci! il a obtenu, et le pire des cas? extrait du livre:la conception et l'analyse de l'algorithme. pourquoi le pire des cas de l'est ni de deux ensembles est vide avant que l'autre contient un seul élément? plutôt que de fractionnement de l'entrée pas exactement deux demi?
    • encore une question, pourquoi à chaque itération prend exactement O(n)? pourriez-vous expliquer en détail?

    InformationsquelleAutor amit