¿Existe un sistema detrás de la magia del análisis de algoritmos?

Hay un montón de preguntas acerca de cómo analizar el tiempo de ejecución de algoritmos (véase, por ejemplo, el tiempo de ejecución-análisis y algoritmo de análisis ). Muchos son similares, por ejemplo, aquellos que solicitan un análisis de costos de bucles anidados o algoritmos de dividir y conquistar, pero la mayoría de las respuestas parecen estar hechas a medida.

Por otro lado, las respuestas a otra pregunta general explican el panorama general (en particular con respecto al análisis asintótico) con algunos ejemplos, pero no cómo ensuciarse las manos.

¿Existe un método estructurado y general para analizar el costo de los algoritmos? El costo puede ser el tiempo de ejecución (complejidad del tiempo), o alguna otra medida de costo, como el número de comparaciones ejecutadas, la complejidad del espacio u otra cosa.

^{Se supone que esto se convertirá en una pregunta de referencia que puede usarse para señalar a los principiantes; de ahí su alcance más amplio de lo habitual. Tenga cuidado de dar respuestas generales, presentadas didácticamente, que se ilustran con al menos un ejemplo, pero que sin embargo cubren muchas situaciones. ¡Gracias!}

Traducción de código a las matemáticas

Dada una (más o menos) semántica operativa formal , puede traducir el código de un algoritmo (pseudo-) literalmente en una expresión matemática que le da el resultado, siempre que pueda manipular la expresión en una forma útil. Esto funciona bien para los aditivos medidas costo, tales como el número de comparaciones, permutas, las declaraciones, los accesos a memoria, los ciclos de algunas necesidades máquina abstracta, y así sucesivamente.

Ejemplo: comparaciones en Bubblesort

Considere este algoritmo que clasifica una matriz dada A:

 bubblesort(A) do                   1
  n = A.length;                     2
  for ( i = 0 to n-2 ) do           3
    for ( j = 0 to n-i-2 ) do       4
      if ( A[j] > A[j+1] ) then     5
        tmp    = A[j];              6
        A[j]   = A[j+1];            7
        A[j+1] = tmp;               8
      end                           9
    end                             10
  end                               11
end                                 12

Digamos que queremos realizar el análisis de algoritmo de clasificación habitual, es decir, contar el número de comparaciones de elementos (línea 5). Notamos de inmediato que esta cantidad no depende del contenido de la matriz A, solo de su longitud . Entonces podemos traducir los bucles (anidados) literalmente en sumas (anidadas); la variable de bucle se convierte en la variable de suma y el rango se transfiere. Obtenemos:$n$for

$\qquad\displaystyle C_{\text{cmp}}(n) = \sum_{i=0}^{n-2} \sum_{j=0}^{n-i-2} 1 = \dots = \frac{n(n-1)}{2} = \binom{n}{2}$ ,

donde es el costo por cada ejecución de la línea 5 (que contamos).$1$

Ejemplo: Swaps en Bubblesort

Denotaré por el subprograma que consiste en líneas hacia y por los costos para ejecutar este subprograma (una vez).$P_{i,j}$ij$C_{i,j}$

Ahora supongamos que queremos contar los intercambios , es decir con qué frecuencia se ejecuta . Este es un "bloque básico", que es un subprograma que siempre se ejecuta atómicamente y tiene un costo constante (aquí, ). Contratar tales bloques es una simplificación útil que a menudo aplicamos sin pensar o hablar de ello.$P_{6,8}$$1$

Con una traducción similar a la anterior, llegamos a la siguiente fórmula:

$\qquad\displaystyle C_{\text{swaps}}(A) = \sum_{i=0}^{n-2} \sum_{j=0}^{n-i-2} C_{5,9}(A^{(i,j)})$ .

$A^{(i,j)}$ denota el estado de la matriz antes de la iteración de .$(i,j)$$P_{5,9}$

Tenga en cuenta que uso lugar de como parámetro; pronto veremos por qué. No agrego y como parámetros de ya que los costos no dependen de ellos aquí (en el modelo de costo uniforme , es decir); en general, tal vez sí.$A$$n$$i$$j$$C_{5,9}$

Claramente, los costos de dependen del contenido de (los valores y , específicamente) por lo que tenemos que dar cuenta de eso. Ahora nos enfrentamos a un desafío: ¿cómo "desenvolvemos" ? Bueno, podemos hacer explícita la dependencia del contenido de :$P_{5,9}$$A$A[j]A[j+1]$C_{5,9}$$A$

$\qquad\displaystyle C_{5,9}(A^{(i,j)}) = C_5(A^{(i,j)}) + \begin{cases} 1 &, \mathtt{A^{(i,j)}[j] > A^{(i,j)}[j+1]} \\ 0 &, \text{else} \end{cases}$ .

Para cualquier matriz de entrada dada, estos costos están bien definidos, pero queremos una declaración más general; Necesitamos hacer suposiciones más fuertes. Investiguemos tres casos típicos.

1. El peor caso

   Simplemente mirando la suma y notando que , podemos encontrar un límite superior trivial para el costo:$C_{5,9}(A^{(i,j)}) \in \{0,1\}$

   $\qquad\displaystyle C_{\text{swaps}}(A) \leq \sum_{i=0}^{n-2} \sum_{j=0}^{n-i-2} 1 = \frac{n(n-1)}{2} = \binom{n}{2}$ .

   Pero, ¿ puede suceder esto , es decir, hay una para alcanzar este límite superior? Resulta que sí: si ingresamos una matriz ordenada inversamente de elementos distintos por pares, cada iteración debe realizar un intercambio¹. Por lo tanto, hemos derivado el número exacto de permutas de Bubblesort en el peor de los casos .$A$

2. El mejor caso

   Por el contrario, hay un límite inferior trivial:

   $\qquad\displaystyle C_{\text{swaps}}(A) \geq \sum_{i=0}^{n-2} \sum_{j=0}^{n-i-2} 0 = 0$ .

   Esto también puede suceder: en una matriz que ya está ordenada, Bubblesort no ejecuta un solo intercambio.

3. El caso promedio

   El peor y el mejor caso abren una gran brecha. Pero, ¿cuál es el número típico de intercambios? Para responder a esta pregunta, necesitamos definir qué significa "típico". En teoría, no tenemos ninguna razón para preferir una entrada sobre otra, por lo que generalmente asumimos una distribución uniforme sobre todas las entradas posibles, es decir, cada entrada es igualmente probable. Nos restringimos a matrices con elementos distintos por pares y, por lo tanto, asumimos el modelo de permutación aleatoria .

   Entonces, podemos reescribir nuestros costos así²:

   $\qquad\displaystyle \mathbb{E}[C_{\text{swaps}}] = \frac{1}{n!} \sum_{A} \sum_{i=0}^{n-2} \sum_{j=0}^{n-i-2} C_{5,9}(A^{(i,j)})$

   Ahora tenemos que ir más allá de la simple manipulación de sumas. Al observar el algoritmo, notamos que cada intercambio elimina exactamente una inversión en (solo intercambiamos vecinos³). Es decir, el número de permutas realizadas en es exactamente el número de inversiones de . Por lo tanto, podemos reemplazar las dos sumas internas y obtener$A$$A$$\operatorname{inv}(A)$$A$

   $\qquad\displaystyle \mathbb{E}[C_{\text{swaps}}] = \frac{1}{n!} \sum_{A} \operatorname{inv}(A)$ .

   Por suerte para nosotros, se ha determinado que el número promedio de inversiones es

   $\qquad\displaystyle \mathbb{E}[C_{\text{swaps}}] = \frac{1}{2} \cdot \binom{n}{2}$

   cual es nuestro resultado final Tenga en cuenta que esto es exactamente la mitad del costo del peor de los casos.

1. Tenga en cuenta que el algoritmo se formuló cuidadosamente para que "la última" iteración i = n-1del bucle externo que nunca hace nada no se ejecute.
2. " " es una notación matemática para "valor esperado", que aquí es solo el promedio.$\mathbb{E}$
3. En el camino, aprendemos que ningún algoritmo que solo intercambia elementos vecinos puede ser asintóticamente más rápido que Bubblesort (incluso en promedio): el número de inversiones es un límite inferior para todos estos algoritmos. Esto se aplica, por ejemplo, al orden de inserción y al orden de selección .

El metodo general

Hemos visto en el ejemplo que tenemos que traducir la estructura de control a las matemáticas; Presentaré un conjunto típico de reglas de traducción. También hemos visto que el costo de cualquier subprograma puede depender del estado actual , es decir (aproximadamente) los valores actuales de las variables. Dado que el algoritmo (generalmente) modifica el estado, el método general es un poco engorroso de observar. Si comienza a sentirse confundido, le sugiero que vuelva al ejemplo o invente el suyo.

Denotamos con el estado actual (imagínelo como un conjunto de asignaciones variables). Cuando ejecutamos un programa que comienza en el estado , terminamos en el estado ( termina siempre ).$\psi$P$\psi$$\psi / \mathtt{P}$P

• Declaraciones individuales

  Dada una sola declaración S;, le asigna costos . Esto será típicamente una función constante.$C_S(\psi)$

• Expresiones

  Si tiene una expresión Ede la forma E1 ∘ E2(por ejemplo, una expresión aritmética donde ∘puede ser suma o multiplicación, suma los costos de forma recursiva:

  $\qquad\displaystyle C_E(\psi) = c_{\circ} + C_{E_1}(\psi) + C_{E_2}(\psi)$ .

  Tenga en cuenta que

  • el costo de operación puede no ser constante pero depende de los valores de y y$c_{\circ}$$E_1$$E_2$
  • la evaluación de expresiones puede cambiar el estado en muchos idiomas,

  entonces puede que tenga que ser flexible con esta regla.

• Secuencia

  Dado un programa Pcomo secuencia de programas Q;R, agrega los costos a

  $\qquad\displaystyle C_P(\psi) = C_Q(\psi) + C_R(\psi / \mathtt{Q})$ .

• Condicionales

  Dado un programa Pde la forma if A then Q else R end, los costos dependen del estado:

  $\qquad\displaystyle C_P(\psi) = C_A(\psi) + \begin{cases} C_Q(\psi/\mathtt{A}) &, \mathtt{A} \text{ evaluates to true under } \psi \\ C_R(\psi/\mathtt{A}) &, \text{else} \end{cases}$

  En general, la evaluación Apuede muy bien cambiar el estado, de ahí la actualización de los costos de las sucursales individuales.

• For-Loops

  Dado un programa Pdel formulario for x = [x1, ..., xk] do Q end, asignar costos

  $\qquad\displaystyle C_P(\psi) = c_{\text{init_for}} + \sum_{i=1}^k c_{\text{step_for}} + C_Q(\psi_i \circ \{\mathtt{x := xi\}})$

  donde es el estado antes de procesar el valor , es decir, después de la iteración con el establecimiento de , ..., .$\psi_i$Qxixx1xi-1

  Tenga en cuenta las constantes adicionales para el mantenimiento del bucle; se debe crear la variable de bucle ( ) y asignarle sus valores ( ). Esto es relevante ya que$c_{\text{init_for}}$$c_{\text{step_for}}$

  • calcular el próximo xipuede ser costoso y
  • un forbucle con cuerpo vacío (por ejemplo, después de simplificar en el mejor de los casos con un costo específico) no tiene costo cero si realiza iteraciones.

• Mientras-Loops

  Dado un programa Pdel formulario while A do Q end, asignar costos

  $\qquad\displaystyle C_P(\psi) \\\qquad\ = C_A(\psi) + \begin{cases} 0 &, \mathtt{A} \text{ evaluates to false under } \psi \\ C_Q(\psi/\mathtt{A}) + C_P(\psi/\mathtt{A;Q}) &, \text{ else} \end{cases}$

  Al inspeccionar el algoritmo, esta recurrencia a menudo se puede representar muy bien como una suma similar a la de for-loops.

  Ejemplo: considere este breve algoritmo:

  while x > 0 do    1
    i += 1          2
    x = x/2         3
  end               4
  

  Al aplicar la regla, obtenemos

  $\qquad\displaystyle C_{1,4}(\{i := i_0; x := x_0\}) \\\qquad\ = c_< + \begin{cases} 0 &, x_0 \leq 0 \\ c_{+=} + c_/ + C_{1,4}(\{i := i_0 + 1; x := \lfloor x_0/2 \rfloor\}) &, \text{ else} \end{cases}$

  con algunos costos constantes para las declaraciones individuales. Suponemos implícitamente que estos no dependen del estado (los valores de y ); Esto puede o no ser cierto en la "realidad": ¡piense en desbordamientos!$c_{\dots}$ix

  Ahora tenemos que resolver esta recurrencia para . Notamos que ni el número de iteraciones ni el costo del cuerpo del bucle dependen del valor de , por lo que podemos descartarlo. Nos quedamos con esta recurrencia:$C_{1,4}$i

  $\qquad\displaystyle C_{1,4}(x) = \begin{cases} c_> &, x \leq 0 \\ c_> + c_{+=} + c_/ + C_{1,4}(\lfloor x/2 \rfloor) &, \text{ else} \end{cases}$

  Esto resuelve con medios elementales para

  $\qquad\displaystyle C_{1,4}(\psi) = \lceil \log_2 \psi(x) \rceil \cdot (c_> + c_{+=} + c_/) + c_>$ ,

  reintroducir simbólicamente el estado completo; if , entonces .$\psi = \{ \dots, x := 5, \dots\}$$\psi(x) = 5$

• Llamadas de procedimiento

  Dado un programa Pde la forma M(x)para algunos parámetros xdonde Mes un procedimiento con parámetro (nombrado) p, asignar costos

  $\qquad\displaystyle C_P(\psi) = c_{\text{call}} + C_M(\psi_{\text{glob}} \circ \{p := x\})$ .

  Observe nuevamente la constante adicional (que de hecho podría depender de !). Las llamadas a procedimientos son costosas debido a cómo se implementan en máquinas reales y, a veces, incluso dominan el tiempo de ejecución (por ejemplo, evaluar la recurrencia del número de Fibonacci ingenuamente).$c_{\text{call}}$$\psi$

  Paso por alto algunos problemas semánticos que podría tener con el estado aquí. Deberá distinguir el estado global y las llamadas locales a procedimientos. Supongamos que solo pasamos el estado global aquí y obtenemos Mun nuevo estado local, inicializado estableciendo el valor de pto x. Además, xpuede ser una expresión que (generalmente) suponemos que se evalúa antes de pasarla.

  Ejemplo: considere el procedimiento

  fac(n) do                  
    if ( n <= 1 ) do         1
      return 1               2
    else                     3
      return n * fac(n-1)    4
    end                      5
  end                        
  

  Según la (s) regla (s), obtenemos:

  $\qquad\displaystyle\begin{align*} C_{\text{fac}}(\{n := n_0\}) &= C_{1,5}(\{n := n_0\}) \\ &= c_{\leq} + \begin{cases} C_2(\{n := n_0 \}) &, n_0 \leq 1 \\ C_4(\{n := n_0 \}) &, \text{ else} \end{cases} \\ &= c_{\leq} + \begin{cases} c_{\text{return}} &, n_0 \leq 1 \\ c_{\text{return}} + c_* + c_{\text{call}} + C_{\text{fac}}(\{n := n_0 - 1\}) &, \text{ else} \end{cases} \end{align*}$

  Tenga en cuenta que no tenemos en cuenta el estado global, ya que facclaramente no accede a ninguno. Esta recurrencia particular es fácil de resolver

  $\qquad\displaystyle C_{\text{fac}}(\psi) = \psi(n) \cdot (c_{\leq} + c_{\text{return}}) + (\psi(n) - 1) \cdot (c_* + c_{\text{call}})$

Hemos cubierto las características del lenguaje que encontrará en el pseudocódigo típico. Tenga cuidado con los costos ocultos al analizar pseudocódigo de alto nivel; En caso de duda, despliegue. La notación puede parecer engorrosa y ciertamente es una cuestión de gustos; Sin embargo, los conceptos enumerados no pueden ser ignorados. Sin embargo, con un poco de experiencia podrá ver de inmediato qué partes del estado son relevantes para qué medida de costo, por ejemplo, "tamaño del problema" o "número de vértices". El resto se puede soltar, ¡esto simplifica las cosas significativamente!

Si cree que esto es demasiado complicado, tenga en cuenta: ¡lo es ! Derivar los costos exactos de los algoritmos en cualquier modelo que esté tan cerca de las máquinas reales como para permitir predicciones de tiempo de ejecución (incluso las relativas) es una tarea difícil. Y eso ni siquiera está considerando el almacenamiento en caché y otros efectos desagradables en máquinas reales.

Por lo tanto, el análisis de algoritmos a menudo se simplifica hasta el punto de ser matemáticamente manejable. Por ejemplo, si no necesita costos exactos, puede sobreestimar o subestimar en cualquier punto (para límites superiores o inferiores): reduzca el conjunto de constantes, elimine los condicionales, simplifique las sumas, etc.

Una nota sobre el costo asintótico

Lo que generalmente encontrará en la literatura y en las webs es el "análisis Big-Oh". El término apropiado es análisis asintótico , lo que significa que en lugar de derivar los costos exactos como lo hicimos en los ejemplos, solo da los costos hasta un factor constante y en el límite (en términos generales, "para grande ").$n$

Esto es (a menudo) justo ya que las declaraciones abstractas tienen algunos costos (generalmente desconocidos) en realidad, dependiendo de la máquina, el sistema operativo y otros factores, y los tiempos de ejecución cortos pueden estar dominados por el sistema operativo que configura el proceso en primer lugar y otras cosas. Entonces te perturba, de todos modos.

Así es como el análisis asintótico se relaciona con este enfoque.

1. Identifique las operaciones dominantes (que inducen costos), es decir, las operaciones que ocurren con mayor frecuencia (hasta factores constantes). En el ejemplo de Bubblesort, una opción posible es la comparación en la línea 5.

   Alternativamente, limite todas las constantes para operaciones elementales por su máximo (desde arriba) resp. su mínimo (desde abajo) y realice el análisis habitual.

2. Realice el análisis utilizando los recuentos de ejecución de esta operación como costo.
3. Al simplificar, permita estimaciones. Tenga cuidado de permitir solo estimaciones desde arriba si su objetivo es un límite superior ( ) resp. desde abajo si desea límites inferiores ( ).$O$$\Omega$

Asegúrese de comprender el significado de los símbolos de Landau . Recuerde que tales límites existen para los tres casos ; el uso de no implica un análisis del peor de los casos.$O$

Otras lecturas

Hay muchos más desafíos y trucos en el análisis de algoritmos. Aquí hay algunas lecturas recomendadas.

• ¿Cómo crear el tiempo de ejecución de los algoritmos?
  ¿Cómo describir algoritmos, probarlos y analizarlos?
• ¿Por qué usar comparaciones en lugar de tiempo de ejecución para comparar dos algoritmos?
  ¿Cómo podemos suponer que las operaciones básicas en números toman tiempo constante?
  ¿Qué constituye una unidad de tiempo en el análisis de tiempo de ejecución?
• Resolver o aproximar relaciones de recurrencia para secuencias de números
• Conceptos básicos del análisis amortizado

Hay muchas preguntas etiquetadas en el análisis de algoritmos que utilizan técnicas similares a esta.

Recuentos de ejecución de declaraciones

Hay otro método, defendido por Donald E. Knuth en su serie The Art of Computer Programming . A diferencia de traducir todo el algoritmo en una fórmula , funciona independientemente de la semántica del código en el lado de "poner las cosas juntas" y permite ir a un nivel inferior solo cuando es necesario, comenzando desde una vista de "ojo de águila". Cada declaración puede analizarse independientemente del resto, lo que lleva a cálculos más claros. Sin embargo, la técnica se presta bien a un código bastante detallado, no a un seudocódigo de nivel superior.

El método

Es bastante simple en principio:

1. Asigne a cada declaración un nombre / número.
2. Asigne a cada declaración algún costo .$S_i$$C_i$
3. Determine para cada instrucción su número de ejecuciones .$S_i$$e_i$

4. Calcular costos totales

   $\qquad\displaystyle C = \sum_{i} e_i \cdot C_i$ .

Puede insertar estimaciones y / o cantidades simbólicas en cualquier punto, debilitando las resp. generalizando el resultado en consecuencia.

Tenga en cuenta que el paso 3 puede ser arbitrariamente complejo. Por lo general, es allí donde debe trabajar con estimaciones (asintóticas) como " " para obtener resultados.$e_{77} \in O(n \log n)$

Ejemplo: búsqueda de profundidad primero

Considere el siguiente algoritmo de recorrido de gráfico:

dfs(G, s) do
  // assert G.nodes contains s
  visited = new Array[G.nodes.size]     1
  dfs_h(G, s, visited)                  2
end 

dfs_h(G, s, visited) do
  foo(s)                                3
  visited[s] = true                     4

  v = G.neighbours(s)                   5
  while ( v != nil ) do                 6
    if ( !visited[v] ) then             7
      dfs_h(G, v, visited)              8
    end
    v = v.next                          9
  end
end

Suponemos que el gráfico (no dirigido) viene dado por listas de adyacencia en los nodos . Sea el número de aristas.$\{0,\dots,n-1\}$$m$

Con solo mirar el algoritmo, vemos que algunas declaraciones se ejecutan con la misma frecuencia que otras. Presentamos algunos marcadores de posición , y para los recuentos de ejecución :$A$$B$$C$$e_i$

$\qquad\begin{array}{c|ccccccccc} i & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline e_i & A & A & B & B & B & B+C & C & B-1 & C \end{array}$

En particular, ya que cada llamada recursiva en la línea 8 provoca una llamada en la línea 3 (y una es causada por la llamada original desde ). Además, porque la condición debe verificarse una vez por iteración, pero luego una vez más para abandonarla.$e_8 = e_3-1$foodfs$e_6 = e_5 + e_7$while

Está claro que . Ahora, durante una prueba de corrección, mostraríamos que se ejecuta exactamente una vez por nodo; es decir, . Pero luego, iteramos sobre cada lista de adyacencia exactamente una vez y cada borde implica dos entradas en total (una para cada nodo incidente); obtenemos iteraciones en total. Con esto, derivamos la siguiente tabla:$A=1$foo$B = n$$C = 2m$

$\qquad\begin{array}{c|ccccccccc} i & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline e_i & 1 & 1 & n & n & n & 2m + n & 2m & n-1 & 2m \end{array}$

Esto nos lleva a costos totales de exactamente

$\qquad\begin{align*} C(n,m) = (C_1 + C_2 - C_8) &+\ n \cdot (C_3 + C_4 + C_5 + C_6 + C_8) \\ &+\ 2m \cdot (C_6 + C_7 + C_9) \;. \end{align*}$

Al crear instancias de valores adecuados para el podemos derivar más costos concretos. Por ejemplo, si queremos contar los accesos a la memoria (por palabra), usaríamos$C_i$

$\qquad\begin{array}{c|ccccccccc} i & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline C_i & n & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 1 \end{array}$

y obten

$\qquad\displaystyle C_{\text{mem}}(n,m) = 3n + 4m$ .

Otras lecturas

Ver al final de mi otra respuesta .

El análisis de algoritmos, como la demostración de teoremas, es en gran medida un arte (por ejemplo, hay programas simples (como el problema de Collatz ) que no sabemos cómo analizar). Podemos convertir un problema de complejidad del algoritmo en uno matemático, como lo respondió Raphael de manera exhaustiva , pero luego, para expresar un límite sobre el costo de un algoritmo en términos de funciones conocidas, nos quedamos para:

1. Utilice técnicas que conocemos de los análisis existentes, como encontrar límites basados ​​en recurrencias que entendemos o sumas / integrales que podemos calcular.
2. Cambie el algoritmo a algo que sepamos analizar.
3. Proponga un enfoque completamente nuevo.