pourquoi est l'heure de la complexité du tri à bulles est le meilleur cas est O(n)
J'en ai déduit la complexité du temps de tri à bulles dans son meilleur des cas, selon la méthode utilisée dans le livre ALGORITHMES 2.2. Mais la réponse s'est avéré être O(n^2).
Voici mon dérivation, de l'espoir, quelqu'un peut m'aider à trouver où est le mal:
public void bubbleSort(int arr[]) {
for(int i = 0, len = arr.length; i < len - 1; i++) {
for(int j = 0; j < len - i - 1; j++) {
if(arr[j + 1] < arr[j])
swap(arr, j, j + 1);
}
}
}
Statements cost times
i = 0,len = arr.length c1 1
i < len - 1 c2 n
i++ c3 n - 1
j = 0 c4 n - 1
j < len - i - 1 c5 t1(i=0) + t1(i=1) + ... + t1(i = n-2)
j++ c6 t2(i=0) + t2(i=1) + ... + t2(i = n-2)
arr[j + 1] < arr[j] c7 t3(i=0) + t3(i=1) + ... + t3(i = n-2)
swap(arr, j, j + 1) c8 t4(i=0) + t4(i=1) + ... + t4(i = n-2)
T(n) = c1 + c2n + c3(n - 1) + c4(n - 1) + c5t5 + c6t6 + c7t7 + c8t8
= c1 + c2n + c3(n - 1) + c4(n - 1) + c5[t1(i=0) + t1(i=1) + ... + t1(i = n-2)] + c6[t2(i=0) + t2(i=1) + ... + t2(i = n-2)] + c7[t3(i=0) + t3(i=1) + ... + t3(i = n-2)] + c8[t4(i=0) + t4(i=1) + ... + t4(i = n-2)];
au mieux de sa fonte, la séquence est déjà positif avant de les trier. Puis t8 doit être 0.
T(n) = c1 + c2n + c3(n - 1) + c4(n - 1) + c5[t1(i=0) + t1(i=1) + ... + t1(i = n-2)] + c6[t2(i=0) + t2(i=1) + ... + t2(i = n-2)] + c7[t3(i=0) + t3(i=1) + ... + t3(i = n-2)]
Le temps de la complexité est O(n^2)
OriginalL'auteur Wendy.Huang | 2012-09-20
Vous devez vous connecter pour publier un commentaire.
Votre mise en œuvre
manque de contrôle s'il y a un swap dans l'intérieur de la boucle, et le sortir de la boucle externe si il n'y en avait pas.
Qui contrôle rend-il possible que le meilleur des cas (déjà un tableau trié) est O(n), puisqu'il n'y a pas de swaps dans la boucle interne lors de l'exécution de la première fois.
Lors de l'analyse d'algorithmes, cependant, il est préférable de ne rien prendre pour acquis, à l'exception de la bare-bones mise en œuvre. Dans ce cas, nous devons assumer la bulle ne sera pas mis en œuvre comme une version optimisée qui casse la boucle si elle n'a jamais swaps de toutes les valeurs.
Vrai. Mais pour le tri à Bulles, au moins certains auteurs (par exemple, wikipédia) inclure la vérification de la définition.
OriginalL'auteur Daniel Fischer
Je ne suis pas sûr de ce que vous comptez. En général, quand vous parlez de comparaison des algorithmes de tri vous devez compter le nombre de comparaisons. Tri à bulles est considéré comme tel. Dans ce cas, l'algorithme présenté est O(n^2).
Si vous comptez le nombre de contrats de swaps de ses O(1) ou peut-être même on pourrait dire O(0). Il est cependant rare d'analyser tri à Bulles comme ça.
Mais vous pouvez très facilement améliorer la Bulle pour obtenir O(N) dans le meilleur des cas. E. g par l'introduction d'un drapeau
swap_was_made
. Si sa faux à la fin de l'intérieurefor
vous pouvez terminer. Sur meilleur des cas, il permettra de réduire la complexité à O(N) (une boucle intérieure). Dans le cas de la juste répartition uniforme il coupe le moyen ou attendu de la complexité à O(N^2/2) ... Mais s'il vous plaît vérifiez me je suis peut-être mal. De ne pas avoir fait maths ici.OriginalL'auteur luk32
Le meilleur des cas pour le tri à bulles est lorsque les éléments sont déjà triés.
La mise en oeuvre habituelle donne O(n^2) temps de complexité pour le mieux, en moyenne, dans le pire des cas.
Nous pouvons modifier le tri à bulles en vérifiant si le tableau est trié ou non(un swap indiquerait un tableau non trié) à chaque itération.
Dès que le tableau est trouvé pour être triés(si pas de swap) de contrôle des sorties de boucles ou d'une boucle continue de s'exécuter jusqu'à la longueur-1.
Et la même chose est vraie pour le tri par insertion ainsi!
OriginalL'auteur Viraj Singh