algorithm - bubble - ¿Por qué la burbuja ordena O(n ^ 2)?

sorting algorithms

Question

int currentMinIndex = 0;

for (int front = 0; front < intArray.length; front++)
{
    currentMinIndex = front;

    for (int i = front; i < intArray.length; i++)
    {
        if (intArray[i] < intArray[currentMinIndex])
        {
            currentMinIndex = i;
        }
    }

    int tmp = intArray[front];
    intArray[front] = intArray[currentMinIndex];
    intArray[currentMinIndex] = tmp;
}

El ciclo interno itera: n + (n-1) + (n-2) + (n-3) + ... + 1 vez.

El ciclo externo se itera: n veces.

Entonces obtienes n * (la suma de los números 1 an)

¿No es eso n * (n * (n + 1) / 2) = n * ((n ^ 2) + n / 2)

¿Cuál sería (n ^ 3) + (n ^ 2) / 2 = O (n ^ 3)?

Estoy seguro de que estoy haciendo esto mal. ¿Por qué no es O (n ^ 3)?

Answer 1

Cómo se calcula básicamente N ...

• Cada línea: +1

• Cada bucle * N

  Así que empiezas a agregar números al primer ciclo ahora que tienes N + 1, sigues adelante y eventualmente obtienes N * N o N ^ 2 por el tiempo más algún número. Retirar el número ya que generalmente es insignificante en comparación con N.

Casi N es una representación de todos los elementos en el ciclo, como 1,2,3 ... N. Entonces, simplemente representa un número no cuántas veces un bucle, bucles.

Answer 2

El ciclo interno itera n veces (en el peor de los casos):

for(int i = front; i < intArray.length; i++)

El ciclo externo itera n veces:

for(int front = 0; front < intArray.length; front++)

Por lo tanto, O (n ^ 2)

Answer 3

Su ciclo interno se está iterando, EN TOTAL, como dijiste n + (n-1) + (n-2) + (n-3) + ... + 1 vez. Entonces es O (n + (n-1) + (n-2) + (n-3) + ... + 1) = O (n (n + 1) / 2) = O (n ^ 2)

Answer 4

Tiene razón en que el bucle externo itera n veces y el bucle interno itera n veces también, pero usted cuenta dos veces el trabajo. Si cuentas el trabajo total realizado al sumar el trabajo realizado en cada iteración del bucle de nivel superior, obtienes que la primera iteración no funciona, la segunda n - 1, la tercera n - 2, etc., desde la última. la iteración del bucle de nivel superior tiene el bucle interno haciendo n - i trabajo.

Alternativamente, puede contar el trabajo realizado al multiplicar la cantidad de trabajo realizado por el ciclo interno multiplicado por el número total de veces que se ejecuta dicho ciclo. El ciclo interno funciona O (n) en cada iteración, y el ciclo externo se ejecuta para O (n) iteraciones, por lo que el trabajo total es O (n ² ).

Está cometiendo un error al intentar combinar estas dos estrategias. Es verdad que el bucle externo no funciona la primera vez, luego n - 1, luego n - 2, etc. Sin embargo, no se multiplica este trabajo por n para obtener el total. Eso contaría cada iteración n veces. En cambio, puedes unirlos.

¡Espero que esto ayude!

Answer 5

Solo por el hecho de tener alguna versión de Python de la clase de burbuja ...

def bubble_sort(input):
    n = len(input)
    iterations = 0
    for i in xrange(n, 1, -1):
        for j in range(0, i - 1):
            iterations += 1
            if input[j] > input[j+1]:
                input[j],input[j+1] = input[j+1],input[j]

    print iterations
    return input

Las iteraciones se agregaron al ciclo interno para contar las iteraciones totales. Nada que ver con el tipo de burbuja.

Al pasar una matriz de 5 elementos, se obtienen 15 iteraciones, no 25. Además, cuando se clasifica previamente también da como resultado 15 iteraciones. Pero la complejidad también debe tener en cuenta la comparación y el intercambio.

Answer 6

k=1(sigma k)n = n(n+1)/2
because:
  s = 1 +  2    + ... + (n-1) + n
  s = n + (n-1) + ... + 2     + 1
+)
===================================
  2s = n*(n+1)
   s = n(n+1)/2
in bubble sort, 
(n-1) + (n-2) + ... + 1 + 0 times compares 
which means, k=0(sigma k)n-1
, k=0(sigma k)n-1 equals [k=1(sigma k)n] - n
therefore, n(n+1)/2 - n = n(n-1)/2
which is 1/2(n^2-n) => O(1/2(n^2-n))
in big O notation, we remove constant, so
O(n^2-n)
n^2 is larger than n
O(n^2)