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

22

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

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

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

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

Дан
источник
Вопрос в обозначениях для асимптотического анализа функций или в использовании асимптотической сложности времени? Я думаю, что вопрос о последнем, но первое предложение (и цитата из Кнута) звучат как о первом. О()
ShreevatsaR
2
Кстати, не относящийся к вашему историческому вопросу, но пункт, который не является полностью историческим: Роберт Седжвик в Принстоне (который случайно сделал свою докторскую степень при Кнуте) в нескольких выступлениях предостерегал против записи «большого О», которую он называет «теорией алгоритмов». ", предпочитая вместо Кнута стиль" анализа алгоритмов "(то есть с фактическими константами). Смотрите, например, эти слайды (первые 21 слайдов). Это не совсем то же самое, что отталкиваться от асимптотического анализа и рекомендовать настенное время, но, ну, вроде как. И это важный момент.
ShreevatsaR
Вы читали этот раздел в истории Википедии (нотации Бахмана – Ландау, Харди и Виноградова) ?
drzbir

Ответы:

2

в вопросах истории обычно есть тонкие нюансы, и определить конкретный документ, в котором представлена ​​конкретная концепция, нелегко, поскольку он имеет тенденцию распространяться на многих участников и иногда переоткрывается независимо, когда неясные ранние ссылки не обязательно распространяются (фундаментальные идеи таковы) , но история в основном идет примерно так: нотация Ландау - это старый математический формализм (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

ВЗН
источник
4
Это не похоже на ответ на вопрос, который был задан. Вопрос был: «Какие первые статьи по информатике использовали big-O?» Ответ должен определить некоторые документы. Я не вижу цитируемых здесь работ, которые бы являлись кандидатами на ответ на вопрос. Сказать «как правило, есть тонкие нюансы, и определить конкретную статью не так-то просто» - не совсем ответ. И, конечно, была статья, которая была первой - она ​​должна быть (по принципу упорядочения) - так что вопрос ответим.
DW