Le temps de la Complexité de l'Insertion de Tri

Quelqu'un pourrait-il expliquer pourquoi le tri par insertion a une complexité temporelle de Θ(n2)?

Je suis assez certain que je comprends complexité en temps est un concept, mais je ne comprends pas vraiment comment l'appliquer à cet algorithme de tri. Dois-je viens de regarder de preuves mathématiques pour répondre à cette question?

L'écriture de la preuve mathématique vous-même ne fera que renforcer votre compréhension. Souvent la plus délicate, les pièces sont en fait le programme d'installation. Par exemple, vous devez d'abord préciser si vous souhaitez le pire des cas, la complexité d'un algorithme, ou quelque chose d'autre (par exemple, la moyenne-la complexité de l'affaire). Deuxièmement, vous voulez définir ce qui est considéré comme une opération réelle dans votre analyse. Pour comparaison algorithmes de tri comme le tri par insertion, d'habitude, on définir des comparaisons de prendre O(1) temps et des swaps de prendre O(1) temps. Vous pouvez justifier à vous-même si c'est valide métrique. À partir de ce point, il suffit d'appliquer la définition

OriginalL'auteur Drake Drinnon | 2013-11-07

  1. 10

    En moyenne chaque insertion doit traverser la moitié de la liste triée tout en faisant une comparaison par étape. La liste augmente d'une unité chaque fois.

    Donc de commencer par une liste de longueur 1 et de l'insertion du premier élément pour obtenir une liste de longueur 2, nous avons en moyenne une traversée de 5 (0 ou 1) des lieux. Le reste est de 1,5 (0, 1, ou 2), 2.5, 3.5, ... , n-.5 pour une liste de longueur n+1.

    C'est, par simple algèbre, 1 + 2 + 3 + ... + n - n*.5 = (n(n+1) - n)/2 = n^2 /2 = O(n^2)

    Noter que c'est le cas moyen. Dans le pire des cas, la liste doit être entièrement parcouru (vous êtes toujours à l'insertion de la prochaine-le plus petit élément dans l'ordre croissant de la liste). Ensuite, vous avez 1 + 2 + ... n, qui est toujours en O(n^2).

    Dans le meilleur des cas vous trouver le point d'insertion à l'élément supérieur avec une comparaison, de sorte que vous avez 1+1+1+ (n fois) = O(n).

    La bonne réponse. Je voudrais juste ajouter 2 choses: 1. Une belle série de notes par Peter Crummins existe ici catonmat.net/blog/mit-introduction-to-algorithms-part-one 2. Dans le pire des cas, nous avons la plus insidieuse des intrants. C'est la liste est complètement inverse de tri. Donc à chaque itération aura 'j' traversals. La formule pour calculer le temps T(n) = sum(\theta(j)) pour j = 2:n. (en supposant que la liste est indexée à partir de 1)
    Exactement. C'est pourquoi le tri des implémentations pour le big data en faisant attention aux "mauvais" cas. Vous généralement (et c'est très approximatif règle de pouce) ne souhaitez pas utiliser le tri par insertion si les données peuvent éventuellement se développer à plus d'une centaine.
    Merci De Gènes. Travaillait sur la complexité du temps théoriquement et j'ai été me casser la tête ce Thêta dans la notation asymptotique en fait quantifie. Je suppose donc qu'elle permet de quantifier le nombre de traversals nécessaire. Juste un petit doute, qu'advient-il si l' > ou = opérateurs de la mise en œuvre plus efficace de la mode dans l'un des l'insertion de toutes sortes. Alors comment pouvons-nous changer Theta() notation pour en tenir compte. ou suis-je sur-pensée?
    Vous êtes en droit d'être concerné avec des détails. \O, \Omega, \Theta et al concernent les relations entre les fonctions pas de temps d'exécution. Lorsque nous les utilisons pour décrire les runtimes, l'abstraction de la nature de la participation et de l'autre laisser-aller, en fait des problèmes. Dans la plupart des caractérisations de sorte algoritms la fonction décrite par \S, \Theta, etc est "nombre de comparaisons par rapport au nombre de données d'entrée pour les données causant le pire des cas de la performance". Donc, le moment de l'exécution de la comparaison a déjà été pris en compte de l'analyse. Avec cette définition, le tri par insertion est (comme vous le décrivez) \Theta(n^2).
    Le meilleur des cas est en fait un de moins que N: dans le cas le plus simple une comparaison est nécessaire pour N=2, N=3 et ainsi de suite. Pour le pire des cas le nombre de comparaisons est N*(N-1)/2: dans le cas le plus simple une comparaison est nécessaire pour N=2, trois pour N=3 (1+2), six pour N=4 (1+2+3) et ainsi de suite.

    OriginalL'auteur Gene

  2. 1

    Elle ne s'applique qu'à des tableaux/listes - c'est à dire des structures avec O(n) pour les insertions/délétions. Il peut être différent pour d'autres structures de données. Par exemple, pour skiplists il sera en O(n * log(n)), parce que binaire de recherche est possible en O(log(n)) dans skiplist, mais insérer/supprimer sera constante.

    OriginalL'auteur vladich