Анализ рекурсивных алгоритмов

Анализ рекурсивных алгоритмов Лекция 2 1 Рекурсивные функции (recursive functions) ▪ Рекурсивная ф ункция (recursive function) – функция, в теле которой присутствует вызов самой себя ▪ Алгоритм, основанный на таких функциях, называется рекурсивным алгоритмом (recursive algorithm) function Factorial(n) if n = 1 then return 1 end if return n * Factorial(n - 1) end function function main() print Factorial(4) end function 2 Рекурсивные функции (recursive functions) ▪ Рекурсивная ф ункция (recursive function) – функция, в теле которой присутствует вызов самой себя ▪ Алгоритм, основанный на таких функциях, называется рекурсивным алгоритмом (recursive algorithm) function Factorial(n) if n = 1 then return 1 end if return n * Factorial(n - 1) end function function main() print Factorial(4) end function Factorial(4) return 4 * Factorial(3) 3 24 6 Factorial(3) return 3 * Factorial(2) 2 2 Factorial(2) return 2 * Factorial(1) 1 1 Factorial(1) return 1 3 Стек вызовов функций (call stack) • Системный стек (stack) – память предназначенная для хранения адресов возврата из функций, локальных переменных и передачи аргументов в функции function Factorial(n) 1: if n = 1 then 2: return 1 3: end if 4: return n * Factorial(n - 1) end function Stack Factorial(4) n = 4 Return address 4 push Factorial(4) return 4 * Factorial(3) 3 ▪ Рекурсивные функции могут занимать значительную часть стековой памяти для хранения адресов возврата! ▪ Стек имеет конечный размер: $ ulimit –s 8192 4 Стек вызовов функций (call stack) • Системный стек (stack) – память предназначенная для хранения адресов возврата из функций, локальных переменных и передачи аргументов в функции function Factorial(n) 1: if n = 1 then 2: return 1 3: end if 4: return n * Factorial(n - 1) end function Stack Factorial(4) n = 4 Return address 4 Factorial(3) n = 3 Return address 4 push Factorial(4) return 4 * Factorial(3) 3 Factorial(3) return 3 * Factorial(2) 2 ▪ Рекурсивные функции могут занимать значительную часть стековой памяти для хранения адресов возврата! ▪ Стек имеет конечный размер: $ ulimit –s 8192 5 Стек вызовов функций (call stack) • Системный стек (stack) – память предназначенная для хранения адресов возврата из функций, локальных переменных и передачи аргументов в функции function Factorial(n) 1: if n = 1 then 2: return 1 3: end if 4: return n * Factorial(n - 1) end function 3 Factorial(3) return 3 * Factorial(2) 2 Factorial(2) return 2 * Factorial(1) Stack Factorial(4) Factorial(4) return 4 * Factorial(3) 1 n = 4 Return address 4 Factorial(3) n = 3 Return address 4 Factorial(2) n = 2 push Return address 4 6 Стек вызовов функций (call stack) • Системный стек (stack) – память предназначенная для хранения адресов возврата из функций, локальных переменных и передачи аргументов в функции function Factorial(n) 1: if n = 1 then 2: return 1 3: end if 4: return n * Factorial(n - 1) end function Factorial(4) return 4 * Factorial(3) n = 3 Return address 4 Factorial(2) n = 2 Return address 4 Factorial(1) 2 1 n = 4 Return address 4 Factorial(3) Factorial(3) return 3 * Factorial(2) Factorial(2) return 2 * Factorial(1) Stack Factorial(4) 3 Глубина рекурсивных вызовов (3 вызова) Factorial(1) return 1 n = 1 7 Стек вызовов функций (call stack) • Системный стек (stack) – память предназначенная для хранения адресов возврата из функций, локальных переменных и передачи аргументов в функции function Factorial(n) 1: if n = 1 then 2: return 1 3: end if 4: return n * Factorial(n - 1) end function Stack Factorial(4) n = 4 Return address 4 Factorial(3) n = 3 Return address 4 Factorial(2) Factorial(4) return 4 * Factorial(3) 3 Factorial(3) return 3 * Factorial(2) 2 Factorial(2) return 2 * Factorial(1) 1 1 Factorial(1) return 1 n = 2 Return address 4 При выходе из функции из головы стека извлекается адрес возврата 8 Стек вызовов функций (call stack) • Системный стек (stack) – память предназначенная для хранения адресов возврата из функций, локальных переменных и передачи аргументов в функции function Factorial(n) 1: if n = 1 then 2: return 1 3: end if 4: return n * Factorial(n - 1) end function Stack Factorial(4) n = 4 Return address 4 Factorial(3) n = 3 Return address 4 Factorial(4) return 4 * Factorial(3) 3 Factorial(3) return 3 * Factorial(2) 2 2 Factorial(2) return 2 * Factorial(1) 1 1 Factorial(1) return 1 9 Стек вызовов функций (call stack) • Системный стек (stack) – память предназначенная для хранения адресов возврата из функций, локальных переменных и передачи аргументов в функции function Factorial(n) 1: if n = 1 then 2: return 1 3: end if 4: return n * Factorial(n - 1) end function Stack Factorial(4) n = 4 Return address 4 Factorial(4) return 4 * Factorial(3) 3 6 Factorial(3) return 3 * Factorial(2) 2 2 Factorial(2) return 2 * Factorial(1) 1 1 Factorial(1) return 1 10 Стек вызовов функций (call stack) • Системный стек (stack) – память предназначенная для хранения адресов возврата из функций, локальных переменных и передачи аргументов в функции function Factorial(n) 1: if n = 1 then 2: return 1 3: end if 4: return n * Factorial(n - 1) end function Stack Factorial(4) return 4 * Factorial(3) 3 6 Factorial(3) return 3 * Factorial(2) 2 2 Factorial(2) return 2 * Factorial(1) 1 1 Factorial(1) return 1 11 Виды рекурсии ▪ Линейная рекурсия (linear recursion) – в функции присутствует единственный рекурсивный вызов самой себя ▪ Древовидная рекурсия (нелинейная, non-linear recursion) – в функции присутствует несколько рекурсивных вызовов function Factorial(n) if n = 1 then return 1 end if return n * Factorial(n - 1) end function function Fib(n) if n < 2 then return n end if return Fib(n - 1) + Fib(n - 2) end function 12 Задача сортировки (sorting problem) ▪ Дана последовательность из n ключей 𝑎1 , 𝑎2 , … , 𝑎𝑛 ▪ Требуется упорядочить ключи по неубыванию или по невозрастанию – найти перестановку (i1, i2, …, in ) ключей ▪ По неубыванию (non-decreasing order) 𝑎𝑖 1 ≤ 𝑎𝑖 2 ≤ ⋯ ≤ 𝑎𝑖 𝑛 ▪ По невозрастанию (non-increasing order) 𝑎𝑖 1 ≥ 𝑎𝑖 2 ≥ ⋯ ≥ 𝑎𝑖 𝑛 13 Сортировка слиянием (merge sort) ▪ Сортировка слиянием (merge sort) – асимптотически оптимальный алгоритм сортировки сравнением, основанный на методе декомпозиции («разделяй и властвуй», decomposition) ▪ Требуется упорядочить заданный массив A [1..n ] по неубыванию (non-decreasing order) так, чтобы 𝐴[1] ≤ 𝐴[2] ≤ ⋯ ≤ 𝐴[𝑛] ▪ Алгоритм включает две фазы 1) Разделение (partition) – рекурсивное разбиение массива на меньшие подмассивы, их сортировка 2) Слияние (merge) – объединение упорядоченных массивов в один 14 Сортировка слиянием (merge sort) ▪ Подмассив A [low, high ] делится на две части A [low..mid ] и A [mid + 1, high ] ▪ mid = floor ((low + high ) / 2) 15 Сортировка слиянием (merge sort) Функция Merge сливает упорядоченные подмассивы 𝐴[𝑙𝑜𝑤..𝑚𝑖𝑑] и 𝐴[𝑚𝑖𝑑+1..ℎ𝑖𝑔ℎ] в один отсортированный массив, элементы которого занимают позиции 𝐴[𝑙𝑜𝑤..ℎ𝑖𝑔ℎ] 16 Сортировка слиянием (merge sort) function MergeSort(A[1:n], low, high) if low < high then mid = floor((low + high) / 2) MergeSort(A, low, mid) MergeSort(A, mid + 1, high) Merge(A, low, mid, high) end if end function ▪ Сортируемый массив A [low..high ] разделяется (partition) на две максимально равные по длине части ▪ Первая часть содержит 𝑛/2 элементов, вторая: 𝑛/2 элементов ▪ Подмассивы рекурсивно сортируются 17 Сортировка слиянием (merge sort) function Merge(A[1:n], low, mid, high) for i = low to high do B[i] = A[i] /* Создаем копию массива A */ end for l = low /* Номер первого элемента левого подмассива */ r = mid + 1 /* Номер первого элемента правого подмассива */ i = low while l <= mid and r <= high do if B[l] <= B[r] then A[i] = B[l] l = l + 1 else A[i] = B[r] r = r + 1 end if i = i + 1 end while 18 Сортировка слиянием (merge sort) while l <= mid do /* Копируем оставшиеся элементы из левого подмассива */ A[i] = B[l] l = l + 1 i = i + 1 end while while r <= high do /* Копируем оставшиеся элементы из правого подмассива */ A[i] = B[r] r = r + 1 i = i + 1 end while end function 19 Анализ эффективности алгоритма сортировки слиянием Анализ дерева рекурсивных вызовов 20 Сортировка слиянием (merge sort) while l <= mid do /* Копируем оставшиеся элементы из левого подмассива */ A[i] = B[l] l = l + 1 i = i + 1 end while while r <= high do /* Копируем оставшиеся элементы из правого подмассива */ A[i] = B[r] r = r + 1 i = i + 1 end while end function ▪ Функция Merge требует порядка Θ(n ) ячеек памяти для хранения копии B сортируемого массива ▪ Сравнение и перенос элементов из массива B в массив A требует Θ(n ) 21 Дерево рекурсивных вызовов MergeSort Слияние 2-х подмассивов Слияние 4-х подмассивов Слияние 8-и подмассивов ??? 22 Дерево рекурсивных вызовов MergeSort Слияние 2-х подмассивов Слияние 4-х подмассивов Слияние 8-и подмассивов 23 Дерево рекурсивных вызовов MergeSort Слияние 2-х подмассивов Слияние 4-х подмассивов Слияние 8-и подмассивов ▪ Высота дерева Θ(logn) ▪ На каждом уровне i находится 2𝑖 узлов ▪ Каждый узел требует выполнения 𝑛 𝑖 операций 2 24 Дерево рекурсивных вызовов MergeSort Слияние 2-х подмассивов Слияние 4-х подмассивов ℎ ℎ 𝑖=0 𝑖=0 𝑛 𝑖 𝑇 𝑛 = ෍ 2 𝑖 = ෍ 𝑛 = ℎ + 1 𝑛 = 𝑛 log 2 𝑛 + 𝑛 = Θ(𝑛 log 𝑛). Слияние 8-и 2 подмассивов ▪ Высота дерева Θ(logn) ▪ На каждом уровне i находится 2𝑖 узлов ▪ Каждый узел требует выполнения 𝑛 𝑖 операций 2 25 Анализ эффективности алгоритма сортировки слиянием Решение рекуррентных уравнений 26 Решение рекуррентных уравнений ▪ Время T (n ) работы алгоритма включает время сортировки левого подмассивов длины 𝑛/2 и правого – с числом элементов 𝑛/2 , а также время Θ(n) слияния подмассивов после их рекурсивного упорядочивания 𝑇 𝑛 = 𝑇 𝑛Τ2 + 𝑇 𝑛Τ2 + Θ(𝑛) ▪ Необходимо решить это рекуррентное уравнение – получить выражение для T (n ) без рекуррентности 27 Основной метод (master method) ▪ Рассмотрим решение рекуррентных уравнений, когда исходную задачу размера 𝑛 можно разделить на 𝑎 ≥ 1 подзадач размера 𝑛 / 𝑏 ▪ Будем считать, что для решения задачи размера 1 требуется время 𝑂(1) ▪ Декомпозиция задачи размера 𝑛 и комбинирование (слияние) решений подзадач требует 𝑓(𝑛) единиц времени ▪ Тогда время 𝑇(𝑛) решения задачи размера 𝑛 можно записать как 𝑇(𝑛) = 𝑎𝑇(𝑛 / 𝑏) + 𝑓(𝑛), где 𝑎 ≥ 1, 𝑏 > 1 ▪ Записанное уравнение называется обобщенным рекуррентным уравнением декомпозиции (general divide-and-conquer recurrence) ▪ Решением этого уравнения является порядок роста функции 𝑇(𝑛), который определяется из следующей основной теоремой (master theorem) 28 Основная теорема (master theorem) Теорема. Если в обобщенном рекуррентном уравнении декомпозиции 𝑓(𝑛) = Θ(𝑛𝑑), где 𝑑 ≥ 0, то Пример 1. В рекуррентном уравнении алгоритма сортировки слиянием 𝑇 𝑛 = 2𝑇 𝑛/2 + Θ(𝑛) 𝑎 = 2, 𝑏 = 2, 𝑓(𝑛) = Θ(𝑛) и 𝑑 = 1 Следовательно, имеем случай 𝑎 = 𝑏𝑑 Тогда, следуя теореме, вычислительная сложность сортировки слиянием в худшем случае равна 𝑇(𝑛) = Θ(𝑛𝑑 log 𝑛) = Θ(𝑛 log 𝑛) 29 Основная теорема (master theorem) Пример 2. Для некоторого алгоритма получено рекуррентное уравнение 𝑇(𝑛) = 2𝑇(𝑛/2) + 1 Необходимо найти асимптотически точную оценку для 𝑇(𝑛) Нетрудно заметить: 𝑎 = 2, 𝑏 = 2, 𝑓(𝑛) = Θ(1) и 𝑑 = 0 Поскольку 𝑎 > 𝑏𝑑: 𝑇 𝑛 = Θ 𝑛log𝑏 𝑎 = Θ 𝑛 30 Выполните анализ эффективности алгоритма 31 Литература [DSABook, Глава 2]: Анализ рекурсивных алгоритмов [CLRS, Глава 4]: Разделяй и властвуй [Levitin, Раздел 2.4]: Математический анализ рекурсивных алгоритмов 32