El peor caso de clasificación de burbuja es O (n * n), ¿cómo?

Question

Estoy intentando el tipo de burbuja. Hay 5 elementos y la matriz no está ordenada. El peor caso para burbuja sort shuold sea O (n^2).

Como exmaple estoy usando

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

En este caso la comparación debería ser 5^2 = 25. Uso de verificación manual y el código de , me estoy haciendo el recuento de comparación sea 20. a continuación se presenta el código implemenation ordenamiento de burbuja

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.Length - 1); i++) 
       { 
        count++; 
        if(A[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(); 
    } 
    } 
    } 

salida está siguiendo

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

¿Alguna idea de por qué las matemáticas no son 25?

Answer 1

Recuerde que O (N^2) se simplifica de la expresión real de C * N (2); es decir, hay una constante limitada. Para sortear burbujas, por ejemplo, C sería aproximadamente 1/2 (no exactamente, pero cerrado).

Su recuento de comparación también está desactivado, creo que deberían ser 10 comparaciones por parejas. Pero supongo que podrías considerar el intercambio de elementos para ser otro. De cualquier manera, todo lo que hace es cambiar la parte constante, no la más importante.

Answer 2

La notación Big-O no dice nada sobre cuántas repeticiones (o cuánto tiempo) tomará un algoritmo. Es una indicación del crecimiento tasa de una función a medida que aumenta el número de elementos (generalmente hacia el infinito).

Entonces, en su caso, O (n) simplemente significa que los recursos computacionales de la clase de burbuja crecen por el cuadrado como la cantidad de elementos. Por lo tanto, si tiene el doble de elementos, puede esperar que tome (en el peor de los casos) 4 veces más tiempo (como un superior enlazado). Si tiene 4 veces más elementos, la complejidad aumenta en un factor de 16. Etc.

Para un algoritmo con O (n) complejidad, cinco elementos pueden tomar 25 iteraciones o 25,000 iteraciones. No hay forma de saber sin analizar el algoritmo. En la misma línea, una función con complejidad O (1) (tiempo constante) podría tardar 0,000001 segundos en ejecutarse o dos semanas en ejecutarse.

Answer 3

Si un algoritmo toma las operaciones n^2 - n, aún se simplifica a O(n^2). La notación Big-O es solo una aproximación de cómo se escala el algoritmo, no una medida exacta de la cantidad de operaciones que necesitará para una entrada específica.

Answer 4

Considere: Su ejemplo, clasificación de burbuja de 5 elementos, toma 5x4 = 20 comparaciones. Eso se generaliza a los elementos N de clasificación de burbujas que toman N x (N-1) = N^2 - N comparaciones, y N^2 muy rápidamente obtiene MUCHO más grande que N. De ahí viene O (N^2). (Por ejemplo, para 20 elementos, está viendo 380 comparaciones).

Answer 5

La clasificación de burbuja es un caso específico, y su complejidad total es (n * (n-1)) - que le da el número correcto : 5 elementos conducen a 5 * (5-1) operaciones, que es 20, y es lo que encontraste en el peor de los casos.

El Big O notation simplificado, sin embargo, elimina las constantes y los términos que crecen menos significativamente, y simplemente da O (n^2). Esto hace que sea fácil compararlo con otras implementaciones y algoritmos que pueden no tener exactamente (n * (n-1)), pero cuando se simplifican muestran cómo el trabajo aumenta con una mayor entrada.

Es mucho más fácil comparar la notación Big O, y para grandes conjuntos de datos, las constantes y los términos menores son despreciables.

Answer 6

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

Comparación cuenta para 5 (0: 4) elementos deben ser 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