Тема Рекурентні


^2T(n/ 2)  (n) якщо n 1.

Рішенням цього співвідношення є функція T(n) = Θ(nlgn).

При розгляді рекурентних співвідношень зазвичай вводяться два спрощення. По- перше, приймається, що час роботи алгоритму T(n) визначається лише для цілочислових n, оскільки в більшості алгоритмів кількість вхідних елементів виражається цілим числом.

По-друге, оскільки час роботи алгоритму з вхідними даними фіксованого розміру виражається константою, то в рекурентних співвідношеннях для достатньо малих nзазвичай справедлива тотожність T(n) = Θ(1). Тому для зручності граничні умови рекурентних співвідношень, як правило, відкидаються та приймається, що для малих n час роботи алгоритму є T(n) константою. Тому попереднє рекурентне співвідношення зазвичай буде записуватись як:

T(n)  2T(n/ 2)  (n) , ^(4.2)

без явного зазначення T(n) для малих n.

Метод підстановки

Метод підстановки, який застосовується для рішення рекурентних співвідношень, складається з двох етапів:

робиться припущення про вигляд розв’язку;
за допомогою методу математичної індукції визначаються константи та доводиться, що рішення вірне.

Назва методу пояснює, що припущене рішення підставляється у рекурентне рівняння. Цей метод достатньо потужний, але може застосовуватись лише коли легко можна висунути припущення щодо вигляду розв’язку.

Метод підстановки можна використовувати для визначення або верхньої, або нижньої межі рекурентного співвідношення. В якості прикладу розглянемо верхню границю рекурентного співвідношення:

T(n)  2T(_n/ 2_)  n, ^(4.3)

яке подібне до (4.2). Ми припускаємо, що розв’язок має вигляд T(n) = О(nlgn). Метод полягає в доведенні того, що при придатному виборі константи c>0 виконується

нерівність T(n)  сnlgn. Почнемо з того, що припустимо справедливість цієї нерівності

для _n/ 2_, тобто що виконується співвідношення T_n/ 2_  c_n/ 2_lg_n/ 2_ . Після

підстановки даного виразу в рекурентне співвідношення отримуємо:

Tn  2c_n/ 2_lg_n/ 2_  n cnlgn/ 2 n cnlg n cnlg 2  n

 cnlg n cn n cnlg n,

де остання нерівність виконується при c1.

Тепер, згідно методу математичної індукції, необхідно довести, що цей розв’язок справедливий для граничних умов. Зазвичай для цього достатньо показати, що граничні умови є придатною базою для доведення за індукцією. В рекурентному співвідношенні (4.3) необхідно довести, що сталу cможна обрати достатньо великою для того, щоб співвідношення T(n)  сn lgnвиконувалось й для граничних умов. Така вимога інколи призводить до проблем. Припустимо, що T(1) = 1 – єдина гранична умова цього

несуттєвою: обидва ці числа приблизно рівні половині числа n. Відповідно, можна припустити, що T(n) = О(nlgn) і в цьому випадку, та за допомогою методу підстановки перевірити це припущення.

Інший спосіб знайти розв’язок – зробити грубу оцінку верхньої та нижньої межі, а потім зменшити невизначеність до мінімуму. Наприклад, в рекурентному співвідношенні (4.3) в якості початкової нижньої межі можна було б обрати T(n) = (n), оскільки в ньому присутній доданок n; можна також показати, що грубою верхньою межею буде T(n) = О(n²). Далі верхня межа поступово знижується, а нижня – піднімається доки не буде отримана правильна асимптотична поведінка рішення T(n) = О(nlgn).

Інколи за допомогою простих алгебраїчних перетворень можна звести рекурентне співвідношення до вже відомого випадку. Наприклад, наступне співвідношення:

T(n)  2T_n_ lg n

виглядає досить складним. Проте його можна спростити, виконавши заміну змінних. Для