С энтропией легко справиться. На мой взгляд, это довольно простая и полезная концепция .
По сути, это количественная оценка того, что в среднем вы узнаете из события, такого как подбрасывание монеты, выполнение инструкции ветвления или индексация массива.
Как операция сравнения в середине алгоритма поиска имеет определенную вероятность P взятия одной ветви и 1-P взятия другой.
Предположим, что P равно 1/2, как в бинарном поиске. Затем, если вы берете эту ветвь, вы знаете на 1 бит больше, чем раньше, потому что log (2/1), основание 2, равно 1. С другой стороны, если вы берете другую ветку, вы также изучаете 1 бит.
Чтобы получить среднее количество информации, которую вы изучите, умножьте то, что вы изучаете в первой ветви, на вероятность, которую вы выберете для этой ветви, плюс на то, что вы узнали во второй ветви, умножьте на вероятность этой ветви.
1/2 умножить на 1 бит, плюс 1/2, умножить на 1 бит, 1/2, плюс 1/2 бит или всего 1 бит энтропии. Вот что вы можете усвоить в среднем из этого решения.
С другой стороны, предположим, что вы выполняете линейный поиск в таблице из 1024 записей.
В первом == тесте вероятность ДА равна 1/1024, поэтому энтропия ДА при этом решении равна
1/1024 times log(1024/1)
или 1/1024 * 10 = примерно 1/100 бит.
Так что, если ответ ДА, вы узнаете 10 битов, но вероятность этого составляет около 1 на тысячу.
С другой стороны, НО гораздо вероятнее. Это энтропия
1023/1024 * log(1024/1023)
или примерно 1 раз, примерно ноль = примерно ноль.
Сложите их вместе, и в среднем вы узнаете примерно 1/100 из этого решения.
Вот почему линейный поиск идет медленно. Энтропия (сколько вы можете ожидать усвоить) при каждом решении слишком мала, поскольку вам нужно будет выучить 10 битов, чтобы найти запись в таблице.