algorithm - notacion - ¿Por qué la inserción ordena Θ(n ^ 2) en el caso promedio?

notacion o grande ejercicios resueltos

Question

La clasificación de inserción tiene un tiempo de ejecución que es Ω (n) (cuando la entrada está ordenada) y O (n ² ) (cuando la entrada está ordenada en orden inverso). En promedio, se ejecuta en Θ (n ² ) tiempo.

¿Por qué es esto? ¿Por qué el caso promedio no está más cerca de O (n log n), por ejemplo?

Answer 1

Para responder a esta pregunta, primero determinemos cómo podemos evaluar el tiempo de ejecución de la ordenación por inserción. Si podemos encontrar una buena expresión matemática para el tiempo de ejecución, podemos manipular esa expresión para determinar el tiempo de ejecución promedio.

La observación clave que debemos tener es que el tiempo de ejecución de ordenación de inserción está estrechamente relacionado con el número de inversiones en la matriz de entrada. Una inversión en una matriz es un par de elementos A [i] y A [j] que están en el orden relativo incorrecto, es decir, i <j, pero A [j] <A [i]. Por ejemplo, en esta matriz:

0 1 3 2 4 5

Hay una inversión: los 3 y 2 deben cambiarse. En este conjunto:

4 1 0 3 2

Hay 6 inversiones

• 4 y 1
• 4 y 0
• 4 y 3
• 4 y 2
• 1 y 0
• 3 y 2

Una propiedad importante de las inversiones es que una matriz ordenada no tiene inversiones, ya que cada elemento debe ser más pequeño que todo lo que viene después y más grande que todo lo que viene antes.

La razón por la cual esto es significativo es que existe un vínculo directo entre la cantidad de trabajo realizado en la ordenación por inserción y el número de inversiones en la matriz original. Para ver esto, repasemos algunos pseudocódigos rápidos para ordenar por inserción:

• Para i = 2 .. n: (Suponiendo 1-indexación)
  • Establecer j = i - 1.
  • Mientras A [j]> A [j + 1]:
    • Intercambia A [j] y A [j + 1].
    • Establecer j = j - 1.

Normalmente, al determinar la cantidad total de trabajo realizado por una función como esta, podemos determinar la cantidad máxima de trabajo realizado por el bucle interno, y luego multiplicarlo por el número de iteraciones del bucle externo. Esto dará un límite superior, pero no necesariamente un límite estrecho. Una mejor forma de dar cuenta del trabajo total realizado es reconocer que hay dos fuentes de trabajo diferentes:

• El ciclo externo, que cuenta 2, 3, ..., n, y
• El bucle interno, que realiza swaps.

Ese bucle externo siempre funciona Θ (n). El bucle interno, sin embargo, realiza una cantidad de trabajo proporcional al número total de intercambios realizados en todo el tiempo de ejecución del algoritmo. Para ver cuánto trabajará ese bucle, necesitaremos determinar cuántos swaps totales se realizan en todas las iteraciones del algoritmo.

Aquí es donde entran las inversiones. Observe que cuando se ejecuta la ordenación por inserción, siempre intercambia elementos adyacentes en la matriz, y solo intercambia los dos elementos si forman una inversión. Entonces, ¿qué ocurre con el número total de inversiones en la matriz después de realizar un intercambio? Bueno, gráficamente, tenemos esto:

 [---- X ----] A[j] A[j+1] [---- Y ----]

Aquí, X es la parte de la matriz que viene antes del par intercambiado y Y es la parte de la matriz que viene después del par intercambiado.

Supongamos que intercambiamos A [j] y A [j + 1]. ¿Qué pasa con el número de inversiones? Bueno, consideremos alguna inversión arbitraria entre dos elementos. Hay 6 posibilidades:

• Ambos elementos están en X, o ambos elementos están en Y, o un elemento está en X y un elemento está en Y. Entonces la inversión todavía está allí, ya que no movimos ninguno de esos elementos.
• Un elemento está en X o Y y el otro es A [j] o A [j + 1]. Entonces la inversión todavía está allí, ya que los ordenamientos relativos de los elementos no han cambiado, incluso si sus posiciones absolutas pudieran tener.
• Un elemento es A [j] y el otro A [j + 1]. Luego la inversión se elimina después del intercambio.

Esto significa que después de realizar un intercambio, disminuimos el número de inversiones exactamente en una, porque solo ha desaparecido la inversión del par adyacente. Esto es muy importante por la siguiente razón: si comenzamos con I inversiones, cada intercambio disminuirá el número exactamente en uno. Una vez que no quedan inversiones, no se realizan más intercambios. ¡Por lo tanto, el número de intercambios es igual al número de inversiones !

Dado esto, podemos expresar con precisión el tiempo de ejecución de la ordenación por inserción como Θ (n + I), donde I es el número de inversiones de la matriz original. Esto coincide con nuestros límites de tiempo de ejecución originales: en una matriz ordenada, hay 0 inversiones, y el tiempo de ejecución es Θ (n + 0) = Θ (n), y en una matriz ordenada inversa, hay n (n - 1) / 2 inversiones, y el tiempo de ejecución es Θ (n + n (n-1) / 2) = Θ (n ² ). ¡Hábil!

Entonces ahora tenemos una manera súper precisa de analizar el tiempo de ejecución de ordenación de inserción dado un conjunto particular. Veamos cómo podemos analizar su tiempo de ejecución promedio. Para hacer esto, necesitaremos hacer una suposición sobre la distribución de las entradas. Dado que el ordenamiento por inserción es un algoritmo de clasificación basado en la comparación, los valores reales de la matriz de entrada en realidad no son importantes; solo su ordenamiento relativo realmente importa. En lo que sigue, voy a suponer que todos los elementos de la matriz son distintos, aunque si este no es el caso, el análisis no cambia demasiado. Señalaré dónde van las cosas: guión cuando lleguemos allí.

Para resolver este problema, vamos a introducir un grupo de variables indicadoras de la forma X _ij , donde X _ij es una variable aleatoria que es 1 si A [i] y A [j] forman una inversión y 0 en caso contrario. Habrá n (n - 1) / 2 de estas variables, una para cada par de elementos distintos. Tenga en cuenta que estas variables representan cada inversión posible en la matriz.

Dadas estas X, podemos definir una nueva variable aleatoria I que es igual al número total de inversiones en la matriz. Esto se dará por la suma de las X:

I = Σ X _ij

Estamos interesados ​​en E [I], el número esperado de inversiones en la matriz. Usando la linealidad de la expectativa, esto es

E [I] = E [Σ X _ij ] = Σ E [X _ij ]

Entonces, si podemos obtener el valor de E [X _ij ], podemos determinar el número esperado de inversiones y, por lo tanto, el tiempo de ejecución esperado.

Afortunadamente, dado que todas las X _ij son variables de indicador binarias, tenemos que

E [X _ij ] = Pr [X _ij = 1] = Pr [A [i] y A [j] son ​​una inversión]

Entonces, ¿cuál es la probabilidad, dada una matriz de entrada aleatoria sin duplicados, de que A [i] y A [j] sean una inversión? Bueno, la mitad del tiempo, A [i] será menor que A [j], y la otra mitad del tiempo A [i] será mayor que A [j]. (Si se permiten duplicados, existe un término adicional furtivo para manejar los duplicados, pero lo ignoraremos por el momento). En consecuencia, la probabilidad de que haya una inversión entre A [i] y A [j] es 1 / 2. Por lo tanto:

E [I] = ΣE [X _ij ] = Σ (1/2)

Como hay n (n - 1) / 2 términos en la suma, esto funciona para

E [I] = n (n - 1) / 4 = Θ (n ² )

Y así, en la expectativa, habrá inver (n ² ) inversiones, por lo que en expectativa el tiempo de ejecución será Θ (n ² + n) = Θ (n ² ) . Esto explica por qué el comportamiento de caso medio de ordenación por inserción es Θ (n ² ).

¡Espero que esto ayude!

Answer 2

La mayoría de los algoritmos tienen el promedio de casos igual que el peor de los casos. Para ver por qué es esto, llamemos a O el peor de los casos y Ω al mejor de los casos. Presumiblemente, O> = Ω cuando n va al infinito. Para la mayoría de las distribuciones, el caso promedio va a estar cerca del promedio del mejor y peor caso, es decir, (O + Ω) / 2 = O / 2 + Ω / 2. Como no nos importan los coeficientes, y O> = Ω, esto es lo mismo que O.

Obviamente, esto es una simplificación excesiva. Hay distribuciones de tiempo de ejecución que están sesgadas de manera que la suposición de que el promedio de casos es el promedio del peor de los casos y el mejor de los casos no es válido *. Pero esto debería darte una buena intuición de por qué es esto.

* Como mencionó templatetypedef en los comentarios, algunos ejemplos son quicksort / quickselect, BST lookup (a menos que equilibre el árbol), hash table searchup y el método simplex.

Answer 3

Para divertirme, escribí un programa que analizaba todas las combinaciones de datos para un vector de tamaño n que cuenta las comparaciones y descubrí que el mejor caso es n-1 (todo ordenado) y el peor es (n * (n-1)) / 2.

Algunos resultados para diferentes n:

  n min     ave     max ave/(min+max) ave/max

  2   1     1         1        0.5000
  3   2     2.667     3        0.5334
  4   3     4.917     6        0.5463
  5   4     7.717    10        0.5512
  6   5    11.050    15        0.5525
  7   6    14.907    21        0.5521
  8   7    19.282    28        0.5509
  9   8    24.171    36        0.5493
 10   9    29.571    45        0.5476
 11  10    35.480    55        0.5458
 12  11    41.897    66        0.5441

Parece que el valor promedio sigue min más cerca que max.

EDITAR: algunos valores adicionales

 13  12    48.820    78        0.5424        
 14  13    56.248    91        0.5408

EDITAR: valor por 15

 15  14    64.182   105        0.5393

EDITAR: valores más altos seleccionados

 16  15    72.619   120        -       0.6052
 32  31   275.942   496        -       0.5563
 64  63  1034.772  1953        -       0.5294
128 127  4186.567  8128        -       0.5151
256 255 16569.876 32640        -       0.5077

Hace poco escribí un programa para calcular el número promedio de comparaciones para ordenar por inserción para valores más altos de n. De esto he sacado la conclusión de que cuando n se aproxima al infinito, el caso promedio se acerca al peor de los casos dividido por dos.