Quels sont les premiers articles en informatique qui ont utilisé la complexité temporelle asymptotique?

22

Quand le grand O a-t-il été utilisé pour la première fois en informatique et quand est-il devenu standard? La page Wikipedia à ce sujet cite Knuth, Big Omicron et Big Omega And Big Theta , SIGACT avril-juin 1976, mais le début de cet article se lit comme suit:

La plupart d'entre nous se sont habitués à l'idée d'utiliser la notation pour représenter toute fonction dont l'amplitude est limitée par un temps constant , pour tout grand .f ( n ) nO(f(n))f(n)n

Cette citation indique que l'idée et la notation étaient déjà couramment utilisées.

La page Wikipedia cite également des articles de mathématiques de la fin des années 1800 et du début des années 1900, mais cela ne répond pas tout à fait à la question. En particulier, j'ai entendu des chercheurs qui étaient à l'époque (dans les années 60 et 70, pas à la fin des années 1800) dire que lorsque l'analyse asymptotique a été utilisée pour la première fois, certaines personnes ont reculé, disant que l'heure de l'horloge murale était une meilleure métrique. Cependant, personne à qui j'ai parlé ne peut citer les documents spécifiques qui ont été rejetés comme celui-ci et j'aimerais trouver des preuves qui peuvent confirmer ou infirmer ces histoires.

asymptotics history dan
la source
La question porte-t-elle sur la notation pour l'analyse asymptotique des fonctions, ou sur l'utilisation de la complexité temporelle asymptotique? Je pense que la question porte sur la seconde, mais la première phrase (et la citation de Knuth) semble concerner la première. O()
ShreevatsaR
2
BTW, pas pertinent pour votre question historique, mais un point qui n'est pas entièrement historique: Robert Sedgewick à Princeton (qui a d'ailleurs fait son doctorat sous Knuth) a mis en garde à plusieurs reprises contre la notation "big O" qu'il appelle "théorie des algorithmes" ", préférant plutôt" l'analyse des algorithmes "à la Knuth (c'est-à-dire avec des constantes réelles) Voir par exemple ces diapositives (les 21 premières diapositives). Ce n'est pas tout à fait la même chose que de repousser l'analyse asymptotique et de recommander l'heure de l'horloge murale, mais bon, en quelque sorte. Et c'est un point important.
ShreevatsaR
Avez-vous lu cette section dans l' histoire de Wikipédia (notations Bachmann – Landau, Hardy et Vinogradov) ?
drzbir

Réponses:

2

avec les questions d'histoire, il y a généralement des nuances subtiles et il n'est pas facile de déterminer un document particulier qui a introduit un concept particulier car il a tendance à être réparti sur de nombreux contributeurs et est parfois redécouvert indépendamment lorsque les premières références obscures ne se diffusent pas nécessairement (les idées fondamentales sont comme ça) . mais l'histoire ressemble à peu près à ceci: la notation Landau est un ancien formalisme mathématique (1894 / Bachman) [1] qui a été importé dans CS en tant que "concept clé" vers le début des années 1970. au milieu des années 1970, cela a été quelque peu accepté comme dans votre référence à Knuth et Knuth lui-même a été impliqué dans la diffusion de ce concept.

il est intéressant de noter que son importation dans CS était probablement étroitement liée aux distinctions P vs NP vs Exptime découvertes au début des années 1970 qui étaient très influentes / annoncées dans le domaine. c'est Cobham / Edmonds qui a commencé à définir la classe P au début des années 1970 [3]. il y avait des premières preuves sur Exptime et Expspace par Stockmeyer / Meyer. [2] le théorème de Cook-Levin [4] (1971) a montré la pertinence fondamentale du temps P vs NP, immédiatement soutenu par Karp [5] (1972).

Pocklington était un des premiers mathématiciens qui travaillait en théorie des nombres mais aussi à la pointe de l'informatique. comme dans [3], il souligne:

Cependant, HC Pocklington, dans un article de 1910, [11] [12] a analysé deux algorithmes pour résoudre les congruences quadratiques, et a observé que l'on prenait du temps "proportionnel à une puissance du logarithme du module" et contrastait avec celui qui prenait du temps proportionnelle "au module lui-même ou à sa racine carrée", établissant ainsi explicitement une distinction entre un algorithme qui s'exécutait en temps polynomial et celui qui ne fonctionnait pas.

Derrick Lehmer, professeur de mathématiques à l'Université de Californie à Berkeley, a également été l'un des premiers pionniers de l'analyse de la complexité des algorithmes basés sur la machine pour la théorie des nombres, c'est-à-dire l'affacturage. et il est possible qu'il ait décrit quelque chose comme la complexité de calcul en tenant compte de manière informelle. [6]

un autre cas encore est une lettre "perdue" de Godel à von Neumann de 1956 parlant de mesures de complexité des étapes f (n) d'une machine pour trouver des preuves de taille n . [7]

[1] Historique de la notation Big O / wikipedia

[2] Problèmes de mots nécessitant un temps exponentiel. / Stockmeyer, Meyer (1973)

[3] Historique des classes de temps P / wikipedia

[4] Théorème de Cook-Levin / wikipedia

[5] Karps 21 NP problèmes complets / wikipedia

[6] Machine d'affacturage Lehmer / tamis / wikipedia

[7] Godels a perdu la lettre / RJLipton

vzn
la source
4
Cela ne semble pas répondre à la question posée. La question était "Quels sont les premiers articles en informatique qui ont utilisé le big-O?" Une réponse devrait identifier certains articles. Je ne vois aucun document cité ici qui soit candidat à une réponse à la question. Dire "il y a généralement des nuances subtiles et ce n'est pas facile de déterminer un papier particulier" n'est pas vraiment une réponse. Et il y avait sûrement un document qui était le premier - il doit y en avoir (selon le principe du bon ordre) - donc la question est recevable.
DW