Esempio di caso peggiore di Bubble sort è O (n * n), come?

Sto cercando Bubble sort. Ci sono 5 elementi e l’array non è ordinato. La peggiore delle ipotesi per le bolle sort deve essere O (n ^ 2).

Come un exmaple che sto usando

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

In questo caso il confronto dovrebbe essere 5 ^ 2 = 25. Usando la verifica manuale e il codice, sto ottenendo il conteggio del confronto per essere 20. Di seguito è riportato il codice di implementazione del tipo di bolla

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(); } } } 

L’output sta seguendo

  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

Qualche idea sul perché la matematica non ne esce?

La notazione Big-O non ti dice nulla su quante iterazioni (o quanto tempo) richiederà un algoritmo. È un’indicazione del tasso di crescita di una funzione al crescere del numero di elementi (di solito verso l’infinito).

Quindi, nel tuo caso, O (n 2 ) significa semplicemente che le risorse computazionali del bubble sort crescono di un quadrato come numero di elementi. Quindi, se si dispone di un numero doppio di elementi, ci si può aspettare che richieda (caso peggiore) 4 volte più a lungo (come limite superiore ). Se hai 4 volte più elementi, la complessità aumenta di un fattore di 16. Ecc.

Per un algoritmo con complessità O (n 2 ), cinque elementi potrebbero richiedere 25 iterazioni o 25.000 iterazioni. Non c’è modo di dirlo senza analizzare l’algoritmo. Allo stesso modo, una funzione con complessità O (1) (tempo costante) potrebbe richiedere 0.000001 secondi da eseguire o due settimane da eseguire.

Se un algoritmo prende n^2 - n operazioni, questo è ancora semplificato in O(n^2) . La notazione Big-O è solo un’approssimazione di come l’algoritmo scala, non una misura esatta di quante operazioni avrà bisogno per un input specifico.

Considera: il tuo esempio, l’ordinamento in bolla di 5 elementi, richiede 5×4 = 20 confronti. Ciò generalizza a ordinare N elementi a bolle prende N x (N-1) = N ^ 2 – N confronti, e N ^ 2 ottiene molto rapidamente molto più di N. Ecco da dove viene O (N ^ 2). (Ad esempio, per 20 elementi, stai osservando 380 confronti).

Bubble sort è un caso specifico e la sua completa complessità è (n * (n-1)) – che ti dà il numero corretto: 5 elementi portano a 5 * (5-1) operazioni, che è 20, ed è ciò che trovato nel peggiore dei casi.

La notazione Big O semplificata, tuttavia, rimuove le costanti e i termini meno significativi in ​​crescita e fornisce semplicemente O (n ^ 2). Ciò semplifica il confronto con altre implementazioni e algoritmi che potrebbero non avere esattamente (n * (n-1)), ma quando semplificato mostra come il lavoro aumenta con un input maggiore.

È molto più facile confrontare la notazione Big O e per i grandi set di dati le costanti e i termini minori sono trascurabili.

Ricorda che O (N ^ 2) è semplificato dall’espressione reale di C * N (2); cioè c’è una costante limitata. Ad esempio, per il tipo di bolla C dovrebbe essere circa 1/2 (non esattamente, ma chiuso).

Anche il tuo conteggio dei paragoni è spento, penso, dovrebbero essere 10 confronti a coppie. Ma immagino che potresti considerare lo scambio di elementi come un altro. Ad ogni modo, tutto ciò che fa è cambiare la costante, non la parte più importante.

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

Il conteggio di comparazione per 5 (0: 4) elementi dovrebbe essere 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