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

22

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(fa(n))fa(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.

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()
ShreevatsaR,
2
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

Odpowiedzi:

2

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
4
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