Математическая логика и теория алгоритмов. Стенюшкина В.А. - 69 стр.

рлинга. Из этой формулы следует, что n!=o(nn), n!=ω(2n), log(n!)= Θ(n log n).
Наконец, 2πn (n/е)n≤n!≤ 2πn (n/е) ne1/12n.
       3.4.5 Пример - Числа Фибоначчи Ф(0)=0; Ф(1)=1; Ф(n+1)=Ф(n)+Ф(n-1) ,
n>=2, растут экспоненциально с ростом n. (Начало последовательности: 0, 1, 1,
2, 3, 5, 8, 13, 21, 34, 55,…).

      3.5 Рекуррентные соотношения

      Соотношение, устанавливающее связь между значением функции для
данного значения аргумента и значениями этой функции для меньших значений
аргумента, называется рекуррентным. Например, время работы процедуры, вы-
полняющей сортировку слиянием, удовлетворяет рекуррентному соотношению:
Т(n)=2Т(n/2)+Θ(n), n>1. Решить рекуррентное соотношение – значит с его по-
мощью найти функцию или установить ее асимптотическое поведение. Здесь n
– размер входа; для простоты считаем, что n – степень числа 2. Рассмотрим не-
которые приемы решения рекуррентных соотношений.

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

      Пример – Т(n)=2Т(n/2)+n, где n – степень двойки. Зададимся видом
Т(n)=О (n log n) (это нужно суметь), то есть предположим, что Т(n)≤сnlogn для
некоторого с. Так как достаточно выполнения оценки, начиная с некоторого n,
позаботимся, чтобы с обеспечивало требуемое неравенство при n=2. Предпо-
ложим теперь, что оценка верна для n/2, то есть Т(n/2)≤с(n/2)log(n/2). Подста-
вим ее в соотношение; получим Т(n)≤с(n/2)log(n/2)+n≤сnlog(n/2)+n=сnlog(n)-
сnlog(2)+n+с nlog(n)-сn+n≤сnlog(n) (последний переход – при условии с≥1).
Итак, Т(n)≤сnlog(n), то есть метод индукции прошел. Делаем вывод:
Т(n)=O(nlog(n)).

                            3.5.2 Метод итераций

      Пример – Т(n)=3Т([n/4])+n, где [▪] - целая часть. Подставляя соотношение
в себя, получим Т(n)=n+3Т([n/4])=n+3([n/4])+3Т([n/16])=n+3([n/4])+3([n/16])+
3Т([n/64])))= … ≤n+3n/4+9n/16+27n/64+ … + 3log nΘ(1)≤n∑i=0∝(3/4)i+Θ(nlog43)
                                                    4



=4n+o(n)=O(n). Здесь использовано равенство [ [ n/4 ]/4] = [ n/16 ] и подобные.
Впрочем, округление здесь не влияет на результат. Поскольку после i -ой ите-
рации справа будет содержаться Т([n/4i]) до Т(1) чтобы дойти, нужно [ n/4i]
приравнять 1, то есть получить i>log4n. Но заметив, что [ n/4i] ≤ n/4i, можно
оценить наш ряд геометрической прогрессией со знаменателем (3/4) плюс сла-
гаемое 3 log4n, относящееся к задачам ограниченного размера, и заменить ука-
занное слагаемое на nlog43, что есть o(n).

                          3.5.3 Основной результат