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

159

Hay un montón de preguntas acerca de cómo analizar el tiempo de ejecución de algoritmos (véase, por ejemplo, y ). 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!

Rafael
fuente
3
Gracias al autor (es) de StackEdit por hacer que sea conveniente escribir publicaciones tan largas, y a mis lectores beta FrankW , Juho , Gilles y Sebastian por ayudarme a resolver una serie de fallas que tenían los borradores anteriores.
Raphael
1
Hola @Raphael, estas son cosas maravillosas. ¿Pensé que sugeriría armarlo como un PDF para circular? Este tipo de cosas podría convertirse en una referencia realmente útil.
hablado el
1
@hadsed: ¡Gracias, me alegra que te sea útil! Por ahora, prefiero que se distribuya un enlace a esta publicación. Sin embargo, el contenido del usuario SE está "licenciado bajo cc by-sa 3.0 con atribución requerida" (vea el pie de página) para que cualquiera pueda crear un PDF a partir de él, siempre y cuando se otorgue la atribución.
Raphael
2
No soy especialmente competente en esto, pero ¿es normal que no haya ninguna referencia al teorema del Maestro en ninguna respuesta?
babou
1
@babou No sé qué significa "normal" aquí. Desde mi punto de vista, el teorema maestro no tiene nada que ver aquí: se trata de analizar algoritmos, el teorema maestro es una herramienta muy específica para resolver (algunas) recurrencias (y más o menos). Dado que las matemáticas se han cubierto en otro lugar (por ejemplo, aquí ) he elegido cubrir solo la parte del algoritmo a las matemáticas aquí. Doy referencias a publicaciones que tratan sobre el trabajo de las matemáticas en mi respuesta.
Raphael

Respuestas:

134

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:nfor

Ccmp(n)=i=0n2j=0ni21==n(n1)2=(n2) ,

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).Pi,jijCi,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.P6,81

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

Cswaps(A)=i=0n2j=0ni2C5,9(A(i,j)) .

A(i,j) denota el estado de la matriz antes de la iteración de .(i,j)P5,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í.AnijC5,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 :P5,9AA[j]A[j+1]C5,9A

C5,9(A(i,j))=C5(A(i,j))+{1,A(i,j)[j]>A(i,j)[j+1]0,else .

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:C5,9(A(i,j)){0,1}

    Cswaps(A)i=0n2j=0ni21=n(n1)2=(n2) .

    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:

    Cswaps(A)i=0n2j=0ni20=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í²:

    E[Cswaps]=1n!Ai=0n2j=0ni2C5,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 obtenerAAinv(A)A

    E[Cswaps]=1n!Ainv(A) .

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

    E[Cswaps]=12(n2)

    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.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 ).ψPψψ/PP

  • Declaraciones individuales

    Dada una sola declaración S;, le asigna costos . Esto será típicamente una función constante.CS(ψ)

  • 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:

    CE(ψ)=c+CE1(ψ)+CE2(ψ) .

    Tenga en cuenta que

    • el costo de operación puede no ser constante pero depende de los valores de y ycE1E2
    • 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

    CP(ψ)=CQ(ψ)+CR(ψ/Q) .

  • Condicionales

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

    CP(ψ)=CA(ψ)+{CQ(ψ/A),A evaluates to true under ψCR(ψ/A),else

    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

    CP(ψ)=cinit_for+i=1kcstep_for+CQ(ψi{x:=xi})

    donde es el estado antes de procesar el valor , es decir, después de la iteración con el establecimiento de , ..., .ψiQxixx1xi-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 quecinit_forcstep_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

    CP(ψ) =CA(ψ)+{0,A evaluates to false under ψCQ(ψ/A)+CP(ψ/A;Q), else

    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

    C1,4({i:=i0;x:=x0}) =c<+{0,x00c+=+c/+C1,4({i:=i0+1;x:=x0/2}), else

    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!cix

    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:C1,4i

    C1,4(x)={c>,x0c>+c+=+c/+C1,4(x/2), else

    Esto resuelve con medios elementales para

    C1,4(ψ)=log2ψ(x)(c>+c+=+c/)+c> ,

    reintroducir simbólicamente el estado completo; if , entonces .ψ={,x:=5,}ψ(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

    CP(ψ)=ccall+CM(ψglob{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).ccallψ

    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:

    Cfac({n:=n0})=C1,5({n:=n0})=c+{C2({n:=n0}),n01C4({n:=n0}), else=c+{creturn,n01creturn+c+ccall+Cfac({n:=n01}), else

    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

    Cfac(ψ)=ψ(n)(c+creturn)+(ψ(n)1)(c+ccall)

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Ω

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.

Hay muchas preguntas etiquetadas que utilizan técnicas similares a esta.

Rafael
fuente
1
quizás alguna referencia y ejemplos del teorema maestro (y sus extensiones ) para el análisis asintótico
Nikos M.
@NikosM Está fuera de alcance aquí (ver también los comentarios sobre la pregunta anterior). Tenga en cuenta que hago un enlace a nuestra publicación de referencia sobre la resolución de recurrencias, que presenta Master theorem et al.
Raphael
@ Nikos M: mis $ 0.02: mientras el teorema maestro funciona para varias repeticiones, no lo hará para muchos otros; Existen métodos estándar para resolver las recurrencias. Y hay algoritmos para los cuales ni siquiera tendremos una recurrencia que dé el tiempo de ejecución; Algunas técnicas avanzadas de conteo pueden ser necesarias. Para alguien con buenos antecedentes matemáticos, sugiero el excelente libro de Sedgewick y Flajolet, "Análisis de algoritmos", que tiene capítulos como "relaciones de recurrencia", "funciones generadoras" y "aproximaciones asintóticas". Las estructuras de datos aparecen como ejemplos ocasionales, ¡y el enfoque está en los métodos!
Jay
@Raphael No puedo encontrar ninguna mención en la web para este método de "Traducción de código a las matemáticas" basado en la semántica operativa. ¿Puede proporcionar alguna referencia a un libro, documento o artículo que trate esto más formalmente? O en el caso de que fue desarrollado por usted, ¿tiene algo más en profundidad?
Wyvern666
1
@ Wyvern666 Lamentablemente, no. Lo inventé yo mismo, por lo que cualquiera puede decir que inventa algo como esto. Tal vez yo mismo escriba un trabajo citable en algún momento. Dicho esto, todo el corpus de trabajo en torno a la combinatoria analítica (Flajolet, Sedgewick y muchos otros) es la base de esto. No se molestan con la semántica formal del "código" la mayor parte del tiempo, pero proporcionan las matemáticas para lidiar con los costos aditivos de los "algoritmos" en general. Sinceramente, creo que los conceptos que se presentan aquí no son muy profundos; sin embargo, las matemáticas en las que puedes entrar sí lo son.
Raphael
29

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 .SiCi
  3. Determine para cada instrucción su número de ejecuciones .Siei
  4. Calcular costos totales

    C=ieiCi .

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.e77O(nlogn)

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,,n1}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 :ABCei

i123456789eiAABBBB+CCB1C

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.e8=e31foodfse6=e5+e7while

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=1fooB=nC=2m

i123456789ei11nnn2m+n2mn12m

Esto nos lleva a costos totales de exactamente

C(n,m)=(C1+C2C8)+ n(C3+C4+C5+C6+C8)+ 2m(C6+C7+C9).

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íamosCi

i123456789Cin00110101

y obten

Cmem(n,m)=3n+4m .

Otras lecturas

Ver al final de mi otra respuesta .

Rafael
fuente
8

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.
Ari Trachtenberg
fuente
1
Supongo que no veo cómo esto agrega algo útil y nuevo, además de otras respuestas. Las técnicas ya se describen en otras respuestas. Esto me parece más un comentario que una respuesta a la pregunta.
DW
1
Me atrevo a decir que las otras respuestas demuestran que es no un arte. Es posible que no pueda hacerlo (es decir, las matemáticas), y puede ser necesaria cierta creatividad (en cuanto a cómo aplicar las matemáticas conocidas) incluso si lo es, pero eso es cierto para cualquier tarea. Asumo que no aspiramos a crear nuevas matemáticas aquí. (De hecho, esta pregunta y sus respuestas tenían la intención de desmitificar todo el proceso.)
Rafael
44
@Raphael Ari está hablando de crear una función reconocible como límite, en lugar de “la cantidad de instrucciones ejecutadas por el programa” (que es lo que responde su respuesta). El caso general es un arte: no existe un algoritmo que pueda generar un límite no trivial para todos los algoritmos. El caso común, sin embargo, es un conjunto de técnicas conocidas (como el teorema maestro).
Gilles
@Gilles Si todo para lo que no existe un algoritmo fuera un arte, los artesanos (en particular los programadores) recibirían un pago peor.
Raphael
1
@AriTrachlenberg hace un punto importante, sin embargo, hay una gran cantidad de formas de evaluar la complejidad del tiempo de un algoritmo. Las definiciones de notación Big O en sí mismas insinúan o expresan directamente su naturaleza teórica dependiendo del autor. El "peor de los casos" claramente deja espacio para conjeturas y / o nuevos hechos entre cualquier cantidad de personas en la sala discutiendo. Sin mencionar que la naturaleza misma de las estimaciones asintóticas es algo ... bien inexacta.
Brian Ogden