Le pire exemple de type de bulle est O (n * n), comment?

J’essaye de sortinger les bulles. Il y a 5 éléments et le tableau n’est pas sortingé. Le cas le plus défavorable pour le type à bulle devrait être O (n ^ 2).

Comme exemple, j’utilise

A = {5, 4, 3, 2, 1}

Dans ce cas, la comparaison doit être égale à 5 ^ 2 = 25. En utilisant la vérification manuelle et le code, le nombre de comparaisons est égal à 20. Le code d’implémentation du type à bulle est suivi

using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace SortingAlgo { class Program { public static int[] bubbleSort(int[] A) { bool sorted = false; int temp; int count = 0; int j = 0; while (!sorted) { j++; sorted = true; for (int i = 0; i  A[i+1]) { temp = A[i]; A[i] = A[i+1]; A[i+1] = temp; sorted = false; } Console.Write(count + ". -> "); for(int k=0; k< A.Length; k++) { Console.Write(A[k]); } Console.Write("\n"); } } return A; } static void Main(string[] args) { int[] A = {5, 4, 3, 2, 1}; int[] B = bubbleSort(A); Console.ReadKey(); } } } 

La sortie suit

  1. -> 45321
  2. -> 43521
  3. -> 43251
  4. -> 43215
  5. -> 34215
  6. -> 32415
  7. -> 32145
  8. -> 32145
  9. -> 23145
  10. -> 21345
  11. -> 21345
  12. -> 21345
  13. -> 12345
  14. -> 12345
  15. -> 12345
  16. -> 12345
  17. -> 12345
  18. -> 12345
  19. -> 12345
  20. -> 12345

Avez-vous une idée de la raison pour laquelle les calculs ne vont pas avoir 25 ans?

La notation Big-O ne vous dit rien du nombre d’itérations (ou de la durée) d’un algorithme. C’est une indication du taux de croissance d’une fonction lorsque le nombre d’éléments augmente (généralement vers l’infini).

Donc, dans votre cas, O (n 2 ) signifie simplement que les ressources de calcul de la sorte à bulle croissent de carré en nombre d’éléments. Donc, si vous avez deux fois plus d’éléments, vous pouvez vous attendre à ce qu’il prenne (dans le pire des cas) 4 fois plus longtemps (en tant que limite supérieure ). Si vous avez 4 fois plus d’éléments, la complexité est multipliée par 16. Etc.

Pour un algorithme de complexité O (n 2 ), cinq éléments peuvent prendre 25 itérations, ou 25 000 itérations. Il n’y a aucun moyen de le savoir sans parsingr l’algorithme. Dans le même ordre d’idées, l’exécution d’une fonction de complexité O (1) (temps constant) peut nécessiter 0,000001 seconde ou deux semaines.

Si un algorithme prend n^2 - n opérations, cela rest simplifié en O(n^2) . La notation Big-O n’est qu’une approximation de la façon dont l’algorithme est mis à l’échelle, et non une mesure exacte du nombre d’opérations nécessaires pour une entrée spécifique.

Considérez: Votre exemple, le sorting par bulle de 5 éléments, prend 5×4 = 20 comparaisons. Cela se généralise en sortingant les bulles N éléments prend N x (N-1) = N ^ 2 – N comparaisons, et N ^ 2 devient très rapidement beaucoup plus grand que N. C’est d’où O (N ^ 2). (Par exemple, pour 20 éléments, vous effectuez 380 comparaisons.)

Le sorting à bulles est un cas spécifique, et sa complexité complète est (n * (n-1)) – ce qui vous donne le nombre correct: 5 éléments conduisent à 5 * (5-1) opérations, ce qui correspond à 20 trouvé dans le pire des cas.

La notation simplifiée Big O , cependant, supprime les constantes et les termes dont la croissance est la moins significative, et ne donne que O (n ^ 2). Cela facilite la comparaison avec d’autres implémentations et algorithmes qui peuvent ne pas avoir exactement (n * (n-1)), mais une fois simplifiés, montrent comment le travail augmente avec une entrée plus importante.

Il est beaucoup plus facile de comparer la notation Big O et, pour les grands ensembles de données, les constantes et les termes mineurs sont négligeables.

Rappelez-vous que O (N ^ 2) est simplifié à partir de l’expression réelle de C * N (2); c’est-à-dire qu’il y a une constante bornée. Pour le type à bulles, par exemple, C serait approximativement 1/2 (pas exactement, mais proche).

Votre compte de comparaison est également désactivé, je pense, il devrait être 10 comparaisons par paires. Mais je suppose que vous pourriez envisager d’échanger des éléments. Quoi qu’il en soit, tout ce que cela fait est de changer la constante, pas la partie la plus importante.

 for (int i=4; i>0; i--) { for (int j=0; jA[j+1]){ swapValues(A[j],A[j+1]); ................ 

Le nombre de comparaisons pour 5 (0: 4) éléments doit être 10.

 i=4 - {(j[0] j[1]) (j[1] j[2]) (j[2] j[3]) (j[3] j[4])} - 4 comparisons i=3 - {(j[0] j[1]) (j[1] j[2]) (j[2] j[3])} - 3 comparisons i=2 - {(j[0] j[1]) (j[1] j[2])} - 2 comparisons i=1 - {(j[0] j[1])} - 1 comparison