Сложность песен
-
Сложность песен
- Статья Дональда Кнута, опубликованная в 1977 году
- Шутка о теории сложности вычислений
- Утверждение о превращении длинных песен в повторяющиеся тексты
-
Лемма Кнута 1
- Рефрен уменьшает сложность песни до cN, где c < 1
- Пример создания песен с O(√N) сложностью
-
Прогресс 20-го века
- Появление современных лекарств сократило объем памяти
- Песни произвольной длины и пространственной сложности O(1) существуют
-
Улучшение оценки
- Профессор Курт Айземанн улучшает оценку
- Значение константы c важно для осуществимости
- Средневековая Европа достигла O(2)
-
Коренные американцы
- Коренные американцы достигли O(0)
- Европейцы не были готовы к этому
- Вожди перешли к O(1)
-
Другие реализации
- Гай Л. Стил-младший реализовал O(1)
- Доктор в песне TELNET использовал экспоненциальную рекурсию
-
Педагогический прием
- Дарра Чейви предложила использовать анализ сложности песен для обучения студентов
-
Влияние на науку
- Статья Кнута стала основополагающей для анализа суперполилогарифмических субэкспоненциальных функций