Оценка сложности песен

Кнут делает утверждение, согласно которому «наши далёкие предки изобрели концепцию припева», чтобы уменьшить пространственную сложность песен, которая становится важным фактором, когда необходимо запомнить большое число песен. Лемма 1 в статье устанавливает, что если длина песни обозначена N, то добавление припева уменьшает сложность песни до cN, где коэффициент c < 1[1].

Далее Кнут демонстрирует способ построения песен со сложностью O(${\displaystyle {\sqrt {N}}}$), указывая, что этот подход «позже был улучшен шотландским фермером по имени С. Макдональд»[1].

Ещё более сложный подход дают песни сложностью O(${\displaystyle \log N}$). Это класс песен, известный как «m бутылок пива на стене».

Наконец, в ходе XX века прогресс, стимулируемый тем фактом, что «распространение современных наркотиков привело к потребности в ещё меньшем использовании памяти», привёл к тому, что появились песни произвольной длины с пространственной сложностью O(1), например, песня, определяемая следующим рекуррентным соотношением[1]:

${\displaystyle S_{0}=\epsilon ,S_{k}=V_{k}S_{k-1},\,k\geq 1,}$

${\displaystyle V_{k}=}$ 'That’s the way,' ${\displaystyle U}$ 'I like it,' ${\displaystyle U}$, ${\displaystyle \forall }$ ${\displaystyle k\geq 1}$

${\displaystyle U=}$ 'uh huh,' 'uh huh'

Профессор Курт Айземанн из университета Сан-Диего в письме в журнал Communications of the ACM[3] делает дальнейшие улучшения последней, представлявшейся не подлежащей улучшению оценки, O(1). Он начинает с наблюдения, согласно которому в практических приложениях значение «скрытой константы» c в нотации «O» большого может иметь критическое значение, проводя грань между приемлемостью и неприемлемостью: например, значение константы 10⁸⁰ приведёт к тому, что объём информации превысит ёмкость любого из известных науке средств хранения информации. Далее он отмечает, что уже в средневековой Европе была известна техника, с использованием которой текстовое содержание любой произвольной мелодии может быть описано рекуррентным соотношением ${\displaystyle S_{k}=C_{2}S_{k-1}}$, где ${\displaystyle C_{2}='la'}$, что даёт значение константы c, равное 2. Однако, как оказалось, другая культура достигла абсолютного нижнего предела сложности O(0)! Профессор Айземанн формулирует это следующим образом:

Когда путешественники с «Мейфлауэра» сошли на этот берег, коренные американцы, гордые своими достижениями в теории хранения и доступа к информации, сперва встретили незнакомцев полным молчанием. Это было средством донести их высшее достижение в сложности песен, а именно продемонстрировать, что низший предел c=0 действительно является достижимым.

Оригинальный текст (англ.)[показатьскрыть]

When the Mayflower voyagers first descended on these shores, the native Americans proud of their achievement in the theory of information storage and retrieval, at first welcomed the strangers with the complete silence. This was meant to convey their peak achievement in the complexity of songs, namely the demonstration that a limit as low as c=0 is indeed obtainable.

Однако европейцы оказались неподготовленными к восприятию этого понятия, и индейские вожди, чтобы найти общую почву для передачи своих достижений, впоследствии продемонстрировали подход, описываемый рекуррентным соотношением ${\displaystyle S_{k}=C_{1}S_{k-1}}$, где ${\displaystyle C_{1}='i'}$, с субоптимальной сложностью, которую даёт значение c=1[2][3].

• «The Complexity of Songs», Knuth, Donald E. (1984).
• Перевод статьи.