Связь энтропии сигнала и скорости алгоритма его обработки

[lamer]

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

Пример: линейный поиск в массиве элементов без отношения порядка. Есть искомый элемент $A$, содержащийся не более одного раза, и есть сообщение-массив длиной $N$ вида 0000100, где 0 либо 1 на данной позиции показывает, равен или не равен элемент на данной позиции искомому элементу $A$. Обрабатывая такое сообщение, алгоритм выносит вердикт "не содержит" (множество из единственного элемента 0000...0 ), либо "содержит" (множесто остальных сообщений). В случае равновероятности как равенства, так и неравенства на данной позиции, энтропия вердиктов как случайной величины равна:
$H=-\frac{1 }{N+1}\cdot{\operatorname{\log_2}(\frac{1}{N+1})}-\frac{N }{N+1}\cdot{\operatorname{\log_2}(\frac{N}{N+1})}$
Эта величина меньше единицы и стремится к нулю с ростом $N$:

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

Однако брутфорсный алгоритм линейного поиска, как известно, в среднем дает $\frac{N+1}{2}$ шагов. Все его улучшения (типа бинарного поиска) требуют привнесения отношения порядка, а у нас - лишь равен/не равен, т.е. есть отношение эквивалентности.

Выходит, что энтропия вердиктов не равна среднему числу шагов некоего лучшего алгоритма?

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