Hoy he aprendido que el análisis de algoritmos difiere según el modelo computacional. Es algo en lo que nunca he pensado ni oído hablar.
Un ejemplo que me dio, que lo ilustró aún más, por el usuario @chi fue:
Por ejemplo, considere la tarea: dado devuelve . En RAM esto se puede resolver en ya que el acceso a la matriz es de tiempo constante. Usando TMs, necesitamos escanear toda la entrada, por lo que esx i O ( 1 ) O ( n )
Esto me hace preguntarme acerca de los lenguajes funcionales; Según tengo entendido, "los lenguajes funcionales están íntimamente relacionados con el cálculo lambda" (de un comentario de Yuval Filmus aquí ). Entonces, si los lenguajes funcionales se basan en el cálculo lambda, pero se ejecutan en máquinas basadas en RAM, ¿cuál es la forma correcta de realizar análisis de complejidad en algoritmos implementados usando estructuras de datos e idiomas puramente funcionales?
No he tenido la oportunidad de leer Estructuras de datos puramente funcionales, pero he examinado el tema en la página de Wikipedia, y parece que algunas de las estructuras de datos reemplazan a las matrices tradicionales con:
"Las matrices se pueden reemplazar por un mapa o una lista de acceso aleatorio, que admite una implementación puramente funcional, pero el tiempo de acceso y actualización es logarítmico".
En ese caso, el modelo computacional sería diferente, ¿correcto?
Respuestas:
Depende de la semántica de su lenguaje funcional. No puede hacer el análisis de algoritmos en lenguajes de programación de forma aislada, porque no sabe lo que realmente significan las declaraciones. La especificación para su idioma debe proporcionar una semántica suficientemente detallada. Si su idioma especifica todo en términos de cálculo lambda, necesita alguna medida de costo para las reducciones (¿son O (1) o dependen del tamaño del término que reduce?).
Creo que la mayoría de los lenguajes funcionales no lo hacen de esa manera y en su lugar proporcionan declaraciones más útiles como "las llamadas a funciones son O (1), añadiendo al encabezado de una lista es O (1)", cosas así.
fuente