Какие первые статьи по информатике использовали асимптотическую сложность времени?

Когда Big O впервые использовался в информатике и когда он стал стандартом? На этой странице Википедии цитируются Кнут, Большой Омикрон, Большая Омега и Большая Тета , SIGACT, апрель-июнь 1976 года, но начало этой статьи гласит:

Большинство из нас привыкли к идее использования обозначения для обозначения любой функции, величина которой ограничена сверху постоянными временами , для всех больших .f ( n ) $O(f(n))$$f(n)$$n$

Эта цитата указывает, что идея и обозначение уже были в общем пользовании.

На странице Википедии также цитируются математические статьи конца 1800-х и начала 1900-х годов, но это не совсем отвечает на вопрос. В частности, я слышал, как исследователи, которые были тогда (в 60-х и 70-х, а не в конце 1800-х годов), говорили, что, когда асимптотический анализ впервые использовался, некоторые люди отодвигались, говоря, что время настенных часов было лучшим показателем. Тем не менее, никто из тех, с кем я говорил, не может ссылаться на конкретные статьи, которые получили такой откат, и я хотел бы найти доказательства, которые могут подтвердить или опровергнуть эти истории.

в вопросах истории обычно есть тонкие нюансы, и определить конкретный документ, в котором представлена ​​конкретная концепция, нелегко, поскольку он имеет тенденцию распространяться на многих участников и иногда переоткрывается независимо, когда неясные ранние ссылки не обязательно распространяются (фундаментальные идеи таковы) , но история в основном идет примерно так: нотация Ландау - это старый математический формализм (1894 / Bachman) [1], который был импортирован в CS как «ключевая концепция» в начале 1970-х годов. к середине 1970-х это было в некоторой степени принято, как в вашей ссылке на Кнута, и сам Кнут участвовал в распространении этой концепции.

Интересно, что его импорт в CS, вероятно, был тесно связан с различиями между P и NP, и Exptime, обнаруженными в начале 1970-х годов, которые были очень влиятельными / известными в этой области. это был Кобхэм / Эдмондс, который начал определять класс P в начале 1970-х годов. [3] были ранние доказательства о Exptime и Expspace от Stockmeyer / Meyer. [2] Теорема Кука-Левина [4] (1971) показала основную актуальность времени P против NP, что было немедленно подтверждено Карпом [5] (1972).

Ранним математиком, который работал в теории чисел, а также на грани информатики, был Поклингтон. как в [3] это указывает на:

Однако Х. К. Поклингтон в работе 1910 г. [11] [12] проанализировал два алгоритма для решения квадратичных конгруэнций и заметил, что один из них требует времени, «пропорционального степени логарифма модуля», и сравнил его с тем, который потребовал времени. пропорционально «самому модулю или его квадратному корню», таким образом явно проводя различие между алгоритмом, который выполнялся за полиномиальное время, и алгоритмом, который этого не делал.

Еще одним пионером в анализе сложности машинных алгоритмов для теории чисел, т.е. факторинга, был Деррик Лемер, профессор математики в Университете Калифорнии, Беркли, и разработал / проанализировал факторинг "алгоритмы" (реализации на основе сит) еще в 1920-х годах и вполне возможно, что он, возможно, описал что-то вроде вычислительной сложности с факторингом неформальным образом. [6]

еще один случай - это «потерянное» письмо Геделя фон Нейману 1956 года, в котором говорится об измерениях сложности шагов f (n) машины, чтобы найти доказательства размера n . [7]

[1] История больших обозначений / Википедия

[2] Проблемы со словами, требующие экспоненциального времени. / Stockmeyer, Meyer (1973)

[3] P история временного класса / Википедия

[4] Теорема Кука-Левина / Википедия

[5] Карпс 21 NP полный проблемы / Википедия

[6] Лемер факторинг машина / сито / Википедия

[7] Годелс потерял письмо / RJLipton