Докажите нижнюю границу, используя модель сравнения дерева решений

Question

Как бы вы использовали дерево решений, чтобы доказать, что поиск отсортированного списка из n элементов имеет нижнюю границу Omega (log n) с моделью, основанной на сравнении?

Answer 1

Если вам нужно использовать дерево решений ...

Для заданной длины n поведение алгоритма, основанного на сравнении, можно представить в виде дерева решений, в котором каждый листэто результат, который вы получите после последовательности сравнений и результатов, представленных путем к этому листу.

Вы доказали, что в дереве решений с n листьями и коэффициентом ветвления 3 , самый длинный путь к листу должен иметь как минимум ceil (log_3 (n)) внутренних узлов.

Вы можете доказать это индуктивно, демонстрируя, что это такдля n в {1,2,3} , и это подразумевает, что это верно для всех больших n , потому что если у поддерева узла есть n листьев, тоодин из его детей должен иметь по крайней мере n / 3 листьев.

Answer 2

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

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

Дерево, которое разбивает дерево на n одиночных листьев минимальной высоты, представляет собой журнал порядка (n) и поэтому это нижняя граница для любого алгоритма.