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

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

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

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

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

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

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

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