13/20. Продолжительность выбора. Следует сказать несколько слов о том, сколько времени может занять некоторый данный акт выбора, ибо при рассмотрении конкретных случаев занимаемое время может, при первой оценке, показаться слишком большим для практического осуществления. Этот вопрос становится особенно важным, когда надо создавать регулятор для регулирования очень большой системы. Приблизительный подсчет количества выбора, которое на первый взгляд кажется необходимым, может привести к мысли, что осуществление его потребует времени, значительно превосходящего космологические масштабы; и отсюда можно сделать вывод, что производство выбора действительно потребует такого же времени. Однако это совсем не так.
Основные принципы, определяющие продолжительность выбора, были выяснены Шенноном, особенно в его статье <Теория связи в системах засекречивания>. Он показал, что если требуется, выбрать один элемент из N и если выборщик может указать (или как-то иначе определить) только то, входит ли или нет требуемый элемент в некоторое данное множество, то методом, осуществляющим полный выбор при наименьшем числе шагов, будет выбор посредством последовательных дихотомий. Иными словами, выбор сначала должен производиться между группами, а не между элементами. Этот метод значительно быстрее метода последовательного просмотра одного за другим N элементов. А когда N становится очень большим, метод выбора по группам становится почти что несравненно более быстрым. Недостаток места не позволяет должным образом рассмотреть здесь этот важный предмет, но не-обходимо по крайней мере привести пример того, насколько более быстрым является метод дихотомий.
Рассмотрим пример по-настоящему большого выбора. Предположим, что где-то во Вселенной (т. е. в ее части, видимой астрономам) имеется определенный атом; выборщик должен его отыскать. Видимая Вселенная содержит около 100000 000 галактик, каждая из которых содержит около 100 000 000 000 солнц и их систем; каждая солнечная система содержит около 300 000 тел, подобных Земле, а Земля содержит около 1 000 000 000 000 куб. миль. Кубическая миля содержит около 1 000 000 000000 000 000 000; пылинок, каждая из которых содержит около 10 000 000 000 000 000 атомов. И выборщик хочет найти один определенный атом!
Примем это за единицу выбора очень большого масштаба и назовем ее 1 мегапик 1 она равна примерно 1 из 
. Сколько времени займет отыскание одного определенного атома?
Стоит сравнить два способа. По первому способу атомы просматриваются по одному, причем быстродействующий электронный тестер просматривает их по миллиону в секунду. Простой расчет показывает, что число столетий, необходимых для отыскания одного атома, не поместилось бы на этой странице. Следовательно, применение этого-метода обрекает выбор на неудачу (для всех практических целей).
Во втором случае используется (допустим, что это возможно) метод дихотомий. Сначала спрашивают: где находится атом - в этой или в той половине? Затем, взяв указанную половину, спрашивают: в какой из ее половин находится атом? И так далее. Предположим, что это может делаться со скоростью одного шага в секунду.
Сколько времени потребует этот способ? Ответ: немногим более четырех минут! При использовании этого способа успех становится возможен.
Этот пример может сделать убедительным утверждение, что выбор по группам гораздо быстрее выбора путем последовательного просмотра. Более того, именно тогда, когда время, отнимаемое последовательным перебором одного элемента за другим, становится чересчур длинным, метод поиска по группам обнаруживает всю свою способность сокращать требуемое время.
1