Рекурентне співвідношення
Рекурентним співвідношенням називається формула виду an+1=F(an,an-1,...,an-k+1), де F деяка функція від k аргументів, яка дозволяє обчислити наступні члени числової послідовності через значення попередніх членів. Рекурентне співвідношення однозначно визначає послідовність an, якщо вказано k перших членів послідовності. Рекурентне співвідношення є прикладом рекурсивного визначення послідовності.
Приклади
- an+1=an+an-1, a1=1, a2=1.
- Рекурентне співвідношення арифметичної прогресії:
- an+1=an+d.
- Рекурентне співвідношення геометричної прогресії:
- an+1=an·q.
- Рекурентне співвідношення послідовності n!:
- an+1=an·(n+1).
- Рекурентне співвідношення синуса фіксованого кута:
- .
Лінійне однорідне рекурентне співвідношення з постійними коефіцієнтами
Лінійним однорідним рекурентним співвідношенням з постійними коефіцієнтами порядку є рівняння
де всі коефіцієнти постійні.
Ті ж самі коефіцієнти визначають характеристичний многочлен (або "допоміжний многочлен")
- .
Згідно з основною теоремою алгебри існує коренів рівняння . Ці корені відіграють вирішальну роль в знаходженні послідовності, яка відповідає заданому рекурентному співвідношенню.
Якщо всі корені різні, то розв'язок рекурсії має вигляд:
де коефіцієнти визначаються в залежності від значень початкових елементів послідовності .
У випадку коли однакові корені присутні декілька разів (кратні корені) розв'язок рекурсії має інший вигляд. Якщо корінь кратності (для простого кореня ), тоді
де коефіцієнти визначаються з початкових елементів послідовності.
Як приклад можна зауважити, що послідовність Фібоначчі задається лінійним однорідним рекурентним співвідношенням з постійними коефіцієнтами порядку два. Застосування наведеного методу дає формулу Біне.
У комбінаториці
Метод розв'язання комбінаторної задачі зведенням до меншої задачі (або задач) називається методом рекурентних співвідношень, а менша задача найчастіше є задачею відносно меншої кількості предметів.[1]
В інформатиці
Рекурентні співвідношення мають принципове значення в аналізі алгоритмів.[2] [3] Якщо алгоритм влаштований так, що він розбивається на декілька менших підзадач, то можна описати час його роботи з допомогою рекурентного співвідношення.
Простий приклад це час, необхідний алгоритму для пошуку елемента в упорядкованому векторі з елементів, в найгіршому випадку.
Примітивний алгоритм полягає в пошуку зліва направо. Найгіршим випадком,буде ситуація в якій потрібний елемент є останнім. В цьому випадку кількість порівнянь буде .
Найкращий алгоритм для цієї задачі є бінарний пошук. Він полягає в наступному. Треба спочатку перевірити, чи знаходиться елемент в середині вектора. Якщо ні, то будемо перевіряти, чи середній елемент більше або менше шуканого елемента. Після цього половина вектора може бути відкинута, і алгоритм може працювати знову на половині, що залишилась. Кількість порівнянь описується рекурентним співвідношенням:
- ,
що буде близько до функції .
Див. також
Посилання
- Карнаух Т.О. Комбінаторика Архівовано 22 лютого 2014 у Wayback Machine.
- Cormen, T. et al, Introduction to Algorithms, MIT Press, 2009
- R. Sedgewick, F. Flajolet, An Introduction to the Analysis of Algorithms, Addison-Wesley, 2013