Метод уменьшения размера задачи
Метод «уменьшай и властвуй»
Метод уменьшения размера задачи
Метод уменьшения размера задачи
При уменьшении на постоянную величину размер экземпляра задачи снижается на одну и ту же постоянную величину при каждой итерации алгоритма. Обычно эта величина равна единицы, хотя встречается и снижение размера на два – в алгоритмах, которые по-разному работают для экземпляров задач четного и нечетного размера. Рассмотрим в качестве примера задачу вычисления aⁿ для положительных целых показателей степени. Связь между решением экземпляра размером n и экземпляра размером n-1 выражается очевидной формулой aⁿ = a * a↑(n-1).
Метод уменьшения размера задачи
Таким образом, функция f(n) = aⁿ может быть вычислена либо «сверху вниз» с использованием рекурсивного определения f(n) = f(n-1) * a при n>1 и f(n) = a при n=1, либо «снизу вверх» путем умножения a на себя n-1 раз (да, это тот же алгоритм, что и при использовании грубой силы, но мы пришли к нему в результате другого подхода). Уменьшение на постоянный множитель предполагает уменьшение размера экземпляра задачи при каждой итерации алгоритма на один и тот же множитель. В большинстве приложений этот множитель равен двум.
Метод уменьшения размера задачи
В качестве примера вновь обратимся к задаче возведения в степень. Для решения экземпляра задачи размером n – вычисления величины aⁿ - решается задача половинного размера, т.е. вычисляется значение a↑(n/2), которое связано с решением исходной задачи очевидным соотношением aⁿ = (a↑(n/2))². Однако поскольку мы рассматриваем задачу только для целых показателей степени, описанный метод годится только для четных n. Если же n нечетно, то мы должны вычислить a↑(n-1) с использованием правила для четных показателей степени, а затем умножить результат на a.
Метод уменьшения размера задачи
(a↑(n/2))² при n положительном четном, aⁿ = (a↑((n-1)/2))² при нечетном n, большем 1, a при n = 1. При рекурсивном вычислении aⁿ в соответствии с этой формулой и измерении эффективности алгоритма посредством количества выполняемых умножений, следует ожидать, что он принадлежит классу О(log2 n), потому что при каждой итерации размер задачи снижается как минимум вдвое, ценой не более двух умножений . Обратите внимание на отличие этого алгоритма от алгоритма, основанного на методе декомпозиции.
Метод уменьшения размера задачи
Метод декомпозиции решает две задачи возведения в степень с размером n/2: aⁿ = (a↑(n/2)) * (a↑(n/2)) при n > 1, a при n = 1. Алгоритм, основанный на этой формуле, неэффективен (почему?), так что алгоритм на основе предыдущей формулы работает гораздо быстрее. Наконец, при уменьшении переменного размера величина снижения размера задачи изменяется от итерации к итерации. Примером такого алгоритма может служить алгоритм Евклида для вычисления НОД. Этот алгоритм основан на формуле gcd(m, n) = gcd(n, m mod n)
Метод уменьшения размера задачи
Хотя аргументы в правой части уравнения всегда меньше аргументов в левой части (как минимум, начиная со второй итерации алгоритма), они не меньше ни на постоянное значение, ни на постоянный множитель. Применение метода уменьшения размера задачи на единицу используется в сортировке вставкой массива A[n]. Следуя идее метода, полагаем, что задача меньшего размера, а именно сортировка массива A[n-1], уже решена и мы имеем отсортированный массив размером n-1. Очевидно, все, что необходимо, это найти нужную позицию среди отсортированных элементов и вставить туда элемент A[n-1].
Метод уменьшения размера задачи
Имеется три подходящих способа сделать это. Во-первых, мы можем сканировать отсортированный подмассив слева направо, пока не достигнем первого элемента, большего или равного A[n-1], и после этого осуществить вставку непосредственно перед найденным элементом. Во-вторых, мы можем сканировать подмассив справа налево, пока не найдем первый элемент, меньший или равный A[n-1], и затем вставить A[n-1] непосредственно за ним. По сути, оба варианта эквивалентны; на практике обычно используют второй способ, поскольку он лучше работает с отсортированными или почти отсортированными массивами (почему?).
Метод уменьшения размера задачи
Полученный в результате алгоритм сортировки называется простой сортировкой вставкой (straight insertion sort), или просто сортировкой вставкой. Третий способ заключается в применении бинарного поиска для определении позиции вставки элемента A[n-1] в отсортированную часть массива. Получающийся при этом алгоритм носит название бинарной сортировкой вставкой (binary insertion sort).
Метод уменьшения размера задачи
Хотя сортировка вставкой основана на рекурсивном подходе, более эффективной будет ее реализация снизу вверх, т.е. итеративная. Элемент A[i] (начиная с элемента A[0] и заканчивая A[n-1]) вставляется в соответствующее место среди первых i элементов массива (которые к этому моменту уже отсортированы). Однако в отличие от сортировки выбором элемент в общем случае вставляется не в окончательную позицию, которую он будет занимать в полностью отсортированном массиве.
Метод уменьшения размера задачи
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.
