Можно ли по энтропии потока сообщений оценить снизу среднее количество шагов, которым должен обладать лучший из возможных алгоритмов их классификации?
Пример: линейный поиск в массиве элементов без отношения порядка. Есть искомый элемент

, содержащийся не более одного раза, и есть сообщение-массив длиной

вида 0000100, где 0 либо 1 на данной позиции показывает, равен или не равен элемент на данной позиции искомому элементу

. Обрабатывая такое сообщение, алгоритм выносит вердикт "не содержит" (множество из единственного элемента 0000...0 ), либо "содержит" (множесто остальных сообщений). В случае равновероятности как равенства, так и неравенства на данной позиции, энтропия вердиктов как случайной величины равна:

Эта величина меньше единицы и стремится к нулю с ростом

:

Так как энтропия, округленная до целого сверху, есть средняя длина сообщения при оптимальном кодировании сигнала, то, выходит, существует способ проиндексировать каждое сообщение бинарной строкой средней длиной 1, т.е. в среднем всего лишь за один шаг получить правильный ответ-вердикт.
Однако брутфорсный алгоритм линейного поиска, как известно, в среднем дает

шагов. Все его улучшения (типа бинарного поиска) требуют привнесения отношения порядка, а у нас - лишь равен/не равен, т.е. есть отношение эквивалентности.
Выходит, что энтропия вердиктов не равна среднему числу шагов некоего лучшего алгоритма?
Тогда вопрос - как связаны эти величины? Возможно, существует добавочный член в виде сложности самой индексации сообщения бинарными строками оптимального кодирования?