Метод уменьшения размера задачи. Метод «уменьшай и властвуй», страница 4

Метод уменьшения размера задачи

Хотя на самом деле размер массива уменьшается от одной итерации к другой непредсказуемым образом (иногда это уменьшение меньше, чем в два раза, иногда – больше), тщательный математический анализ показывает, что эффективность в среднем случае будет такой же, как если бы уменьшение размера задачи всякий раз было ровно в два раза. Другими словами, в среднем мы получаем линейный алгоритм. В худшем же случае эффективность алгоритма падает до Θ(n²). Хотя кибернетики и открыли алгоритм, который решает задачу выбора за линейное время даже в наихудшем случае, он слишком сложен для практического применения.

Метод уменьшения размера задачи

Интерполяционный поиск. Рассмотрим алгоритм поиска в отсортированном массиве, который называется интерполяционным поиском. В отличие от бинарного поиска, который всегда сравнивает ключ поиска со средним значением отсортированного массива (а следовательно, всегда уменьшает размер задачи вдвое), интерполяционный поиск учитывает значение ключа поиска при определении элемента массива, который будет сравнивается с ключом. В определенном смысле алгоритм имитирует поиск имени в телефонной книге. Если мы ищем в телефонной книге, например, Горбенко – вряд ли мы будем открывать ее в середине или ближе к концу, как поступили бы при поиске Подгорного.

Метод уменьшения размера задачи

Говоря более строго, при выполнении итерации поиска между элементами A[l] (крайний слева) и A[r] (крайний справа), алгоритм предполагает, что значения в массиве растут линейно (отличие от линейности может влиять на эффективность, но не на корректность данного алгоритма). В соответствии с этим предположением, значение v ключа поиска сравнивается с элементом, индекс которого вычисляется (с округлением) как координата x точки на прямой, проходящей через (l, A[l]) и (r, A[r]), координата y которой равна значению v.

Метод уменьшения размера задачи

Логика, лежащая в основе этого метода, проста. Мы знаем, что значения массива возрастают (точнее говоря, не убывают) от A[l] до A[r], но не знаем, как именно. Пусть это возрастание – линейное (простейшая из возможных функциональных зависимостей); в таком случае вычисленное значение индекса – ожидаемая позиция элемента со значением v. После сравнения v с A[x] алгоритм либо прекращает работу (если они равны), либо продолжает поиск тем же способом среди элементов с индексами либо от l до x-1, либо от x+1 до r, в зависимости от того, меньше ли v значения A[x] или больше.

Метод уменьшения размера задачи

Таким образом, на каждой итерации размер задачи уменьшается, но априори мы не знаем, насколько именно. Анализ эффективности данного алгоритма показывает, что интерполяционный поиск в среднем требует менее log2log2n + 1 сравнений ключей при поиске в списке из n случайных значений. Эта функция растет настолько медленно, что для всех реальных практических значений n ее можно считать константой. Однако в наихудшем случае интерполяционный поиск вырождается в линейный, который рассматривается как наихудший из возможных (почему?).

Метод уменьшения размера задачи

Поиск и вставка в бинарное дерево поиска. На каждой итерации алгоритма задача поиска в бинарном дереве поиска сводится к задаче поиска в бинарном дереве меньшего размера. Наиболее разумной мерой размера бинарного дерева поиска является его высота; очевидно, что уменьшение высоты дерева может изменяться от итерации к итерации – это дает нам пример алгоритма с переменным уменьшением размера задачи. Напомню, что эффективность поиска в среднем случае – O(log2n), а в наихудшем случае – O(n). Операция вставки нового ключа практически идентична поиску, поэтому вставка также является примером алгоритма с переменным уменьшением размера задачи и имеет ту же эффективность.