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 , dla wszystkich dużych . $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.

asymptotics history

— Dan
źródło

Czy pytanie dotyczy notacji

do asymptotycznej analizy funkcji, czy też zastosowania asymptotycznej złożoności czasowej? Myślę, że pytanie dotyczy tego drugiego, ale pierwsze zdanie (i cytat z Knutha) brzmią jak opowiadanie o tym pierwszym.

O ()

$O()$

— ShreevatsaR,

BTW, nie ma znaczenia dla twojego pytania historycznego, ale chodzi o to, że nie jest on całkowicie historyczny: Robert Sedgewick z Princeton (który przypadkowo zrobił doktorat pod Knuthem) w wielu rozmowach ostrzegał przed notacją „wielka litera O”, którą nazywa „teorią algorytmów” ”, preferując zamiast tego„ analizę algorytmów ”w stylu Knutha (tj. z rzeczywistymi stałymi). Zobacz np. Te slajdy (pierwsze 21 slajdów). Nie jest to zupełnie to samo, co odrzucanie analizy asymptotycznej i zalecanie czasu naściennego, ale cóż, w pewnym sensie. I to jest ważny punkt.

— ShreevatsaR,

Czy czytałeś ten rozdział w Historii Wikipedii (notacje Bachmanna-Landaua, Hardy'ego i Vinogradowa) ?

— drzbir

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

— vzn
źródło

To nie wydaje się odpowiadać na zadane pytanie. Pytanie brzmiało: „Jakie są pierwsze artykuły informatyczne, które wykorzystywały big-O?” Odpowiedź powinna wskazywać niektóre dokumenty. Nie widzę tu cytowanych artykułów, które mogłyby kandydować na odpowiedź na pytanie. Powiedzenie „są zazwyczaj subtelne niuanse i nie jest łatwo ustalić konkretny artykuł” nie jest tak naprawdę odpowiedzią. I na pewno był papier, który był pierwszy - musi być (zgodnie z zasadą uporządkowania) - więc pytanie jest możliwe do odpowiedzi.

— DW