Antes de leer El arte de la programación de computadoras (TAOCP) , no he considerado estas preguntas profundamente. Usaría pseudocódigo para describir algoritmos, comprenderlos y estimar el tiempo de ejecución solo sobre órdenes de crecimiento. El TAOCP cambia completamente de opinión.
TAOCP usa inglés mezclado con pasos y goto para describir el algoritmo, y usa diagramas de flujo para visualizar el algoritmo más fácilmente. Parece de bajo nivel, pero creo que hay algunas ventajas, especialmente con el diagrama de flujo, que he ignorado mucho. Podemos etiquetar cada una de las flechas con una afirmación sobre el estado actual de las cosas en el momento en que el cálculo atraviesa esa flecha, y hacer una prueba inductiva para el algoritmo. El autor dice:
Es la opinión del autor que realmente comprendemos por qué un algoritmo es válido solo cuando llegamos al punto en que nuestras mentes han llenado implícitamente todas las afirmaciones, como se hizo en la figura 4.
No he experimentado tales cosas. Otra ventaja es que podemos contar la cantidad de veces que se ejecuta cada paso. Es fácil verificar con la primera ley de Kirchhoff. No he analizado exactamente el tiempo de ejecución, por lo que algunos podrían haberse omitido cuando estaba estimando el tiempo de ejecución.
El análisis de las órdenes de crecimiento a veces es inútil. Por ejemplo, no podemos distinguir la clasificación rápida de la clasificación múltiple porque todas son , donde es el número esperado de la variable aleatoria , por lo que debemos analizar la constante, digamos, y E ( T 2 ( n ) ) = A 2 lg n + B 2 n + O ( log n ) , así podemos comparar T 1 y T 2mejor. Y también, a veces debemos comparar otras cantidades, como las variaciones. Solo un análisis aproximado de las órdenes de crecimiento del tiempo de ejecución no es suficiente. Como TAOCP traduce los algoritmos al lenguaje ensamblador y calcula el tiempo de ejecución, es demasiado difícil para mí, por lo que quiero conocer algunas técnicas para analizar el tiempo de ejecución un poco más a fondo, lo que también es útil para lenguajes de nivel superior como C , C ++ o pseudocódigos.
Y quiero saber qué estilo de descripción se usa principalmente en trabajos de investigación y cómo tratar estos problemas.
fuente
Respuestas:
Hay una gran variedad de enfoques factibles. Cuál es el más adecuado depende de
Si el algoritmo es ampliamente conocido y lo utiliza como subrutina, a menudo permanece en un nivel superior. Si el algoritmo es el objeto principal bajo investigación, probablemente quiera ser más detallado. Lo mismo puede decirse de los análisis: si necesita un límite de tiempo de ejecución superior aproximado, procederá de manera diferente a cuando desea un recuento preciso de declaraciones.
Le daré tres ejemplos para el conocido algoritmo Mergesort que, con suerte, ilustrarán esto.
Nivel alto
El algoritmo Mergesort toma una lista, la divide en dos (aproximadamente) partes igualmente largas, se repite en esas listas parciales y combina los resultados (ordenados) para que se ordene el resultado final. En listas simples o vacías, devuelve la entrada.
Este algoritmo es obviamente un algoritmo de clasificación correcto. Dividir la lista y fusionarla se puede implementar en el tiempo , lo que nos da una recurrencia para el peor tiempo de ejecución T ( n ) = 2 T ( nΘ ( n ) . Según el teorema del Maestro, esto se evalúa comoT(n)∈Θ(nlogn).T( n ) = 2 T( n2) +Θ(n) T( n ) ∈ Θ ( n logn )
Nivel medio
El algoritmo Mergesort viene dado por el siguiente pseudocódigo:
Probamos la corrección por inducción. Para listas de longitud cero o uno, el algoritmo es trivialmente correcto. Como hipótesis de inducción, suponga quenorte n > 1 L n + 1 L L
mergesort
funciona correctamente en listas de longitud como máximo para algunos arbitrarios, pero fijos naturales n > 1 . Ahora dejemos que L sea una lista de longitud n + 1 . Por hipótesis de inducción, y mantener (sin disminución) versiones ordenadas de la primera resp. segunda mitad de L después de las llamadas recursivas. Por lo tanto, el ciclo selecciona en cada iteración el elemento más pequeño que aún no se ha investigado y lo agrega ; por lo tanto, es una lista no cada vez más ordenada que contiene todos los elementos deleft
right
while
result
result
left
yright
. El reverso es una versión ordenada no decreciente de , que es el resultado devuelto y deseado.En cuanto al tiempo de ejecución, cuentemos las comparaciones de elementos y las operaciones de lista (que dominan el tiempo de ejecución asintóticamente). Las listas de longitud inferior a dos no causan ninguna. Para las listas de longitud , tenemos esas operaciones causadas por la preparación de las entradas para las llamadas recursivas, las de las llamadas recursivas más el bucle y uno . Ambos parámetros recursivos se pueden calcular con a lo sumo n operaciones de lista cada uno. El bucle se ejecuta exactamente n veces y cada iteración causa como máximo una comparación de elementos y exactamente dos operaciones de lista. La final se puede implementar para usar 2 nn > 1 norte norte 2 n operaciones de lista: cada elemento se elimina de la entrada y se coloca en la lista de salida. Por lo tanto, el recuento de operaciones cumple la siguiente recurrencia:
while
reverse
while
reverse
Como es claramente no decreciente, es suficiente considerar n = 2 k para el crecimiento asintótico. En este caso , la recurrencia se simplifica aT n=2k
Según el teorema del Maestro, obtenemos que se extiende al tiempo de ejecución de .T∈Θ(nlogn)
mergesort
Nivel ultra bajo
Considere esta implementación (generalizada) de Mergesort en Isabelle / HOL :
Esto ya incluye pruebas de buena definición y terminación. Encuentre una prueba de corrección (casi) completa aquí .
Para el "tiempo de ejecución", es decir, el número de comparaciones, se puede configurar una recurrencia similar a la de la sección anterior. En lugar de usar el teorema del Maestro y olvidar las constantes, también puede analizarlo para obtener una aproximación que sea asintóticamente igual a la cantidad verdadera. Puede encontrar el análisis completo en [1]; Aquí hay un bosquejo (no necesariamente se ajusta al código Isabelle / HOL):
Como arriba, la recurrencia para el número de comparaciones es
donde es el número de comparaciones necesarias para fusionar los resultados parciales². Para deshacernos de los pisos y techos, realizamos una distinción entre mayúsculas y minúsculas sobre si n es par:en n
Usando diferencias anidadas hacia adelante / hacia atrás de y e n obtenemos quefn en
.∑k=1n−1(n−k)⋅Δ∇fk=fn−nf1
La suma coincide con el lado derecho de la fórmula de Perron . Definimos las series generadoras de Dirichlet de comoΔ∇fk
que junto con la fórmula de Perron nos lleva a
fuente
La "Disciplina de la programación" de Dijkstra se trata de analizar y probar algoritmos y diseñar para probar. En el prefacio de ese libro, Dijkstra explica cómo un mini lenguaje construido muy simple que está diseñado adecuadamente para ser analizado es suficiente para explicar formalmente muchos algoritmos:
Más tarde, explica cuán pequeño logró obtener su mini idioma.
fuente