Рекурентне співвідношення

Рекурентним співвідношенням називається формула виду 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] Якщо алгоритм влаштований так, що він розбивається на декілька менших підзадач, то можна описати час його роботи з допомогою рекурентного співвідношення.

Простий приклад це час, необхідний алгоритму для пошуку елемента в упорядкованому векторі з елементів, в найгіршому випадку.

Примітивний алгоритм полягає в пошуку зліва направо. Найгіршим випадком,буде ситуація в якій потрібний елемент є останнім. В цьому випадку кількість порівнянь буде .

Найкращий алгоритм для цієї задачі є бінарний пошук. Він полягає в наступному. Треба спочатку перевірити, чи знаходиться елемент в середині вектора. Якщо ні, то будемо перевіряти, чи середній елемент більше або менше шуканого елемента. Після цього половина вектора може бути відкинута, і алгоритм може працювати знову на половині, що залишилась. Кількість порівнянь описується рекурентним співвідношенням:

,

що буде близько до функції .

Див. також

Посилання

  1. Карнаух Т.О. Комбінаторика Архівовано 22 лютого 2014 у Wayback Machine.
  2. Cormen, T. et al, Introduction to Algorithms, MIT Press, 2009
  3. R. Sedgewick, F. Flajolet, An Introduction to the Analysis of Algorithms, Addison-Wesley, 2013
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.