La complejidad del algoritmo está diseñada para ser independiente de los detalles de nivel inferior, pero se basa en un modelo imperativo, por ejemplo, el acceso a la matriz y la modificación de un nodo en un árbol toman O (1) tiempo. Este no es el caso en lenguajes funcionales puros. La lista de Haskell toma tiempo lineal para acceder. La modificación de un nodo en un árbol implica hacer una nueva copia del árbol.
¿Debería haber un modelado alternativo de la complejidad del algoritmo para los lenguajes funcionales?
ST
mónadas).Respuestas:
Si supone que el cálculo es un buen modelo de lenguajes de programación funcionales, entonces uno puede pensar: el cálculo λ tiene una noción aparentemente simple de complejidad temporal: solo cuente el número de pasos de reducción β ( λ x . M ) N → M [ N / x ] .λ λ β ( λ x . M) N→ M[ N/ x]
¿Pero es esta una buena medida de complejidad?
Para responder a esta pregunta, debemos aclarar qué entendemos por medida de complejidad en primer lugar. La tesis de Slot y van Emde Boas da una buena respuesta : cualquier buena medida de complejidad debe tener una relación polinómica con la noción canónica de complejidad temporal definida con las máquinas de Turing. En otras palabras, debe haber un 'razonable' que codifica A partir de lambda términos -calculus a las máquinas de Turing, como para algunas polinomio p , es el caso de que para cada término M de tamaño | M | : M se reduce a un valor en p ( | M |t r ( . ) λ pags METRO El | METROEl | METRO pasos de reducción β exactamente cuando t r ( M ) se reduce a un valor en p ( | t r ( M ) | ) pasos de una máquina Turing.p ( | MEl | ) β t r ( M) p ( | t r ( M) | )
Durante mucho tiempo, no estaba claro si esto se puede lograr en el cálculo λ. Los principales problemas son los siguientes.
No estoy seguro de cuál es la situación para otras estrategias de evaluación. No soy consciente de que se haya llevado a cabo un programa similar para la complejidad del espacio.
fuente
No en realidad no. Siempre contamos las operaciones elementales en algunos modelos de máquina:
Por lo tanto, su pregunta tiene una respuesta simple: arreglar un modelo de máquina y qué "operaciones" contar. Esto te dará una medida. Si desea que los resultados sean comparables a los algoritmos no funcionales, lo mejor sería compilar sus programas en RAM (para el análisis de algoritmos) o TM (para la teoría de la complejidad), y analizar el resultado. Los teoremas de transferencia pueden existir para facilitar este proceso.
fuente
O(1)
cuando realmente esO(log ab)
En lugar de formular su medida de complejidad en términos de alguna máquina abstracta subyacente, puede incluir el costo en las definiciones del lenguaje en sí, esto se llama Dinámica de Costos . Uno atribuye un costo a cada regla de evaluación en el lenguaje, de manera compositiva, es decir, el costo de una operación es una función del costo de sus sub-expresiones. Este enfoque es más natural para los lenguajes funcionales, pero puede usarse para cualquier lenguaje de programación bien definido (por supuesto, la mayoría de los lenguajes de programación no están bien definidos).
fuente