Рекурсия для выполнения алгоритмов разрыва и завоевания

Question

Работа алгоритма разделения и завоевания на определенном уровне может быть упрощена в уравнение:

$ qquad displayStyle o Left (n^d right) cdot left ( frac {a} {b^d} right)^k $

Если $ n $ - это размер проблемы, $ a $ - это количество суб -проблем, $ b $ - это фактор. Размер проблемы разбивается при каждой рекурсии, $ k $ - это уровень и $ d $ является экспонентом для обозначения Big O (линейная, экспоненциальная и т. Д.).

Книга претендует на то, что соотношение превышает одно, сумма работы определяется последним членом на последнем уровне, но если оно меньше одной, то сумма работы определяется первым сроком первого уровня. Может ли кто -нибудь объяснить, почему это правда?

Answer 1

Общая работа дается суммой геометрического прогрессирования. В частности, пусть $ r = a/b^d $, затем общая работа = $ o (n^d) times (1+r+r^2+ ldots+r^p) $, где $ p $ максимальная глубина.

Пусть $ s = (1+r+r^2+ ldots+r^p) $.

Если $ r> 1 $, то $ s = frac {r^p-1} {r-1}+r^p = o (r^p) $.

Если $ r <1 $, то $ s leq 1+r+r^2+ ldots = frac {1} {1-r} = o (1) $.