Jakie są pierwsze artykuły informatyczne, w których zastosowano asymptotyczną złożoność czasu?

Kiedy duże O po raz pierwszy zastosowano w informatyce i kiedy stało się standardem? Strona Wikipedii na ten temat cytuje Knuth, Big Omicron i Big Omega And Big Theta , SIGACT kwiecień-czerwiec 1976 r., Ale na początku tego artykułu czytamy:

Większość z nas przyzwyczaiła się do używania notacji dla dowolnej funkcji, której wielkość jest ograniczona górnymi stałymi czasami f ( n ) , dla wszystkich dużych n .$O(f(n))$$f(n)$$n$

Ten cytat wskazuje, że pomysł i notacja były już w powszechnym użyciu.

Strona Wikipedii przytacza także artykuły matematyczne z przełomu XIX i XX wieku, ale to nie do końca odpowiada na pytanie. W szczególności słyszałem, że badacze, którzy byli w tym czasie (w latach 60. i 70., a nie pod koniec 1800 r.), Powiedzieli, że kiedy po raz pierwszy zastosowano analizę asymptotyczną, niektórzy ludzie cofnęli się, mówiąc, że czas na zegarze ściennym był lepszy. Jednak nikt, z kim rozmawiałem, nie może przytoczyć konkretnych artykułów, które otrzymały taki zwrot i chciałbym znaleźć dowody, które mogłyby potwierdzić lub zaprzeczyć tym historiom.

w przypadku pytań historycznych występują zwykle subtelne niuanse i nie jest łatwo ustalić konkretny artykuł, który wprowadził określoną koncepcję, ponieważ ma tendencję do rozprzestrzeniania się wśród wielu autorów i czasami jest odkrywany niezależnie, gdy niejasne wczesne odniesienia niekoniecznie się rozpowszechniają (takie są podstawowe idee) . ale historia zasadniczo wygląda mniej więcej tak: notacja Landaua to stary formalizm matematyczny (1894 / Bachman) [1], który został zaimportowany do CS jako „kluczowa koncepcja” na początku lat siedemdziesiątych. w połowie lat 70. XX wieku zostało to nieco zaakceptowane, jak w twoim odniesieniu do Knutha, a on sam był zaangażowany w rozpowszechnianie tej koncepcji.

co ciekawe, jego import do CS był prawdopodobnie ściśle związany z różnicami P vs NP vs. Exptime odkrytymi na początku lat 70., które były bardzo wpływowe / zwiastowane w terenie. to Cobham / Edmonds zaczął definiować klasę P na początku lat 70. [3] wczesne dowody na temat Exptime i Expspace autorstwa Stockmeyer / Meyer. [2] twierdzenie Cooka-Levina [4] (1971) wykazało zasadniczą istotność P w stosunku do czasu NP, natychmiast potwierdzone przez Karpa [5] (1972).

wczesnym matematykiem, który pracował w teorii liczb, ale także na granicy informatyki, był Pocklington. jak w [3] wskazuje:

Jednak HC Pocklington w pracy z 1910 r. [11] [12] przeanalizował dwa algorytmy rozwiązywania przystawek kwadratowych i zauważył, że jeden zajmuje czas „proporcjonalny do potęgi logarytmu modułu” i kontrastuje go z tym, który wymaga czasu. proporcjonalny „do samego modułu lub jego pierwiastka kwadratowego”, tym samym wyraźnie rozróżniając algorytm działający w czasie wielomianowym od algorytmu, który tego nie zrobił.

innym wczesnym pionierem w analizowaniu złożoności algorytmów maszynowych dla teorii liczb, tj. faktoringu, był Derrick Lehmer, profesor matematyki na University of California w Berkeley, i budował / analizował „algorytmy” faktoringu (implementacje oparte na sicie) już w latach dwudziestych i możliwe, że opisał coś w rodzaju złożoności obliczeniowej w faktoringu w nieformalny sposób [6].

jeszcze innym przypadkiem jest „zagubiony” list Godela z 1956 r. do von Neumanna, mówiący o pomiarach złożoności kroków f (n) maszyny w celu znalezienia dowodów wielkości n . [7]

[1] Historia dużych notacji / wikipedia

[2] Problemy ze słowami wymagające czasu wykładniczego./ Stockmeyer, Meyer (1973)

[3] Historia klasy czasu P / wikipedia

[4] Twierdzenie Cooka-Levina / wikipedia

[5] Karps 21 NP kompletne problemy / wikipedia

[6] Maszyna faktoringowa / sito Lehmer / wikipedia

[7] Godels stracił literę / RJLipton