¿Cuándo se usó Big O por primera vez en informática y cuándo se convirtió en estándar? La página de Wikipedia sobre esto cita a Knuth, Big Omicron y Big Omega y Big Theta , SIGACT de abril a junio de 1976, pero el comienzo de ese artículo dice
La mayoría de nosotros nos hemos acostumbrado a la idea de usar la notación para representar cualquier función cuya magnitud esté limitada por un tiempo constante f ( n ) , para todos los n grandes .
Esta cita indica que la idea y la notación ya eran de uso común.
La página de Wikipedia también cita documentos de matemáticas de finales de 1800 y principios de 1900, pero eso no responde a la pregunta. En particular, escuché a investigadores que estaban en ese entonces (en los años 60 y 70, no a fines del siglo XIX) decir que cuando se utilizó el análisis asintótico por primera vez, algunas personas retrocedieron, diciendo que el tiempo del reloj de pared era una mejor métrica. Sin embargo, nadie con quien he hablado puede citar los documentos específicos que tuvieron retrocesos como este y me gustaría encontrar evidencia que pueda confirmar o negar estas historias.
fuente
Respuestas:
con las preguntas de historia, generalmente hay sutiles matices y no es fácil determinar un artículo en particular que introdujo un concepto particular porque tiende a extenderse entre muchos contribuyentes y, a veces, se redescubre de forma independiente cuando las primeras referencias oscuras no necesariamente se difunden (las ideas fundamentales son así) . pero la historia básicamente es algo así: la notación de Landau es un antiguo formalismo matemático (1894 / Bachman) [1] que se importó a CS como un "concepto clave" a principios de los años setenta. a mediados de la década de 1970, esto fue algo aceptado como en su referencia de Knuth y el mismo Knuth estuvo involucrado en la difusión de este concepto.
Curiosamente, su importación en CS probablemente estuvo estrechamente relacionada con las distinciones P vs NP vs Exptime descubiertas a principios de la década de 1970 que fueron muy influyentes / anunciadas en el campo. Fue Cobham / Edmonds quien comenzó a definir la clase P a principios de la década de 1970. [3] Hubo pruebas tempranas sobre Exptime y Expspace por Stockmeyer / Meyer. [2] el teorema de Cook-Levin [4] (1971) mostró la relevancia central del tiempo P vs NP, inmediatamente respaldado por Karp [5] (1972).
Pocklington fue uno de los primeros matemáticos que trabajó en teoría de números pero también al borde de la informática. como en [3] señala:
Otro pionero temprano en el análisis de la complejidad de los algoritmos basados en máquinas para la teoría de números, es decir, la factorización, fue Derrick Lehmer, profesor de matemáticas en la Universidad de California, Berkeley, y construyó / analizó "algoritmos" de factorización (implementaciones basadas en tamices) ya en la década de 1920. y es posible que haya descrito algo como la complejidad computacional wrt factoring de manera informal. [6]
otro caso más es una carta de 1956 "perdida" de Godel a von Neumann que habla sobre medidas de complejidad de los pasos f (n) de una máquina para encontrar pruebas de tamaño n . [7]
[1] Historia de notación Big O / wikipedia
[2] Problemas verbales que requieren tiempo exponencial. / Stockmeyer, Meyer (1973)
[3] Historial de clases de tiempo P / wikipedia
[4] Teorema de Cook-Levin / wikipedia
[5] Problemas completos de Karps 21 NP / wikipedia
[6] Máquina de factorización Lehmer / tamiz / wikipedia
[7] Godels perdió carta / RJLipton
fuente