В худшем случае (для латинского алфавита), при котором кто-нибудь, например, все время жужжит («ZZZZ…»), потребуется 26 вопросов для каждой буквы. Итак, мы определили границы, в которых будет происходить передача любой информации. У нас никогда не получится лучше, чем при варианте с одной буквой, и хуже, чем со всеми 26.
Оценка будет точнее, если учесть среднее количество вопросов на каждую букву, то есть средний случай. Сделать это не так трудно. В длинном сообщении на каждую «А» где-нибудь еще придется «Z», на каждую «B» найдется «Y» и так далее. Это значит, что в среднем во всей книге на каждую продиктованную букву надо будет задать 13 вопросов. Умножьте число букв в книге на 13, и вы получите примерную оценку работы при ее написании. Умножьте это на среднее время, которое уходит у помощницы, чтобы произнести букву, и вы получите время, необходимое, чтобы написать книгу.
Отметим, что мы снова оцениваем наш алгоритм – но на сей раз нас интересует не то, действует ли он вообще, а то, насколько быстро он действует. У алгоритма оценивают много разных аспектов, но надежность и эффективность – два важнейших для оценки.
Изменение, внесенное Боби, — сначала спрашивать о распространенных буквах — улучшает ситуацию. Вероятно, получится уложиться в 10‒11 произносимых букв. А с учетом частотности, мы рассчитаем это точнее. Частотность можно уточнить или определить самостоятельно. Возьмите отрывок из любимой книги и посчитайте, сколько раз появляется каждая буква. Потом расположите буквы по порядку, начиная с самой распространенной, и посчитайте вероятность их появления. Средний случай — это число букв, которое необходимо произнести для угадывания одной буквы, вероятность появления которой равна 50%.
Итак, частотный анализ привел к улучшениям, но не слишком значительным, и в худшем случае для выяснения одной буквы все равно надо задать 26 вопросов. Но каждый специалист по информатике знает, что можно существенно улучшить этот процесс. Любая буква выясняется всего за пять вопросов! Гарантированно! И это не средний случай, а худший! Знаете, какие пять вопросов надо задать?
Уложитесь в пять
Смогли вы ответить на этот вопрос или нет, я гарантирую, что вы знаете, о каких вопросах идет речь. Чтобы вспомнить о них, нужно рассмотреть другую задачу.
Давайте сыграем в игру «20 вопросов». Это детская игра, в которой водящий задумывает известного человека, а вы пытаетесь догадаться, кто это, задавая вопросы. Изюминка в том, что отвечать следует только «да» или «нет». Сыграйте в эту игру с другом и обратите внимание, какие вопросы вы задаете. Представим, как может пойти игра.
