В некотором смысле 10! (десять факторных) представляет приблизительную границу между вещами, которые практично вычислять, и вещами, которые не являются.
Это из книги Кнута TAOCP "Основные алгоритмы" (1973). Это все еще допустимое утверждение или вычислительная мощность сделала его устаревшим?
computer-science
taocp
Бон Ами
источник
источник
Ответы:
Это все еще разумно.
10! = 3628880 Каждый последующий шаг увеличивается как минимум на порядок.
Довольно скоро вы говорите о расходах Конгресса.
источник
К счастью, хороший профессор все еще с нами, и лучший способ найти окончательный ответ - написать ему и спросить его мнение.
Тем не менее, я не думаю, что абсолютное число имеет значение так же, как функция, которую представляют факториалы. Независимо от того, осознал ли Кнут в то время это, модель, которую он создал с этим утверждением, очень хорошо работает для того, чтобы оглянуться назад на то, что было практично вычислить в предыдущие десятилетия, и перейти к последующим.
В 1973 году наши возможности по генерированию, хранению, передаче и обработке данных были ограничены до 10! разумная фигура "дальнего края", чтобы стрелять. Я сомневаюсь, что Кнут (или кто-либо еще, если на то пошло) смог бы предсказать экспоненциальные улучшения почти во всем, чем мы наслаждались с тех пор, но факториалы хорошо соответствуют фактическим цифрам.
Я видел это воочию: десять лет назад я работал над проектом, в котором мы разрабатывали способы хранения и обработки около 50 миллионов записей, в то же время размышляя над тем, как бы мы сделали на порядок больше. Десять лет спустя я делаю похожий проект. Мои целевые показатели изменились, все в факторной манере:
Группы, работающие над обоими проектами, собирают гораздо более круглые цифры, чем те, но факториалы не за горами. Googles и Facebook в мире имеют ресурсы для того, чтобы делать то, о чем мой нынешний проект только мечтает, но с того места, где я сижу,
13!
в течение десятилетия или даже меньше, кажется, недостижимым.Я не думал о больших объемах данных в 1992 году, но в ретроспективе сказал, что, вероятно, я бы смотрел на все на один фактор меньше.
источник