Рекуррентное соотношение: Дискретная математика — рекуррентное соотношение

Содержание

Дискретная математика — рекуррентное соотношение

В этой главе мы обсудим, как рекурсивные методы могут выводить последовательности и использоваться для решения задач подсчета. Процедура поиска членов последовательности рекурсивным способом называется рекуррентным отношением . Мы изучаем теорию линейных рекуррентных соотношений и их решения. Наконец, мы вводим производящие функции для решения рекуррентных отношений.

Определение

Рекуррентное отношение – это уравнение, которое рекурсивно определяет последовательность, в которой следующий член является функцией предыдущих членов (выражая Fn как некоторую комбинацию Fi с i<n).

Пример – ряд Фибоначчи – Fn=Fn−1+Fn−2, Ханойская башня – Fn=2Fn−1+1

Линейные рекуррентные отношения

Линейное рекуррентное уравнение степени k или порядка k – это рекуррентное уравнение в формате xn=A1xn−1+A2xn−1+A3xn−1+ dotsAkxnk (An – константа, а Ak neq0) на последовательности чисел как полинома первой степени.

Вот некоторые примеры линейных рекуррентных уравнений –

Рецидив отношений	Начальные значения	Решения
F _n = F _n-1 + F _n-2	a ₁ = a ₂ = 1	Число Фибоначчи
F _n = F _n-1 + F _n-2	а ₁ = 1, а ₂ = 3	Номер Лукаса
F _n = F _n-2 + F _n-3	a ₁ = a ₂ = a ₃ = 1	Падовская последовательность
F _n = 2F _n-1 + F _n-2	a ₁ = 0, a ₂ = 1	Число Пелла

Как решить линейное рекуррентное соотношение

Предположим, что два упорядоченных линейных рекуррентных соотношения имеют вид – Fn=AFn−1+BFn−2, где A и B – действительные числа.

Характеристическое уравнение для вышеуказанного рекуррентного соотношения –

x2−Axe−B=0

Три случая могут возникнуть при поиске корней –

Случай 1 – Если это уравнение учитывается как (x−x1)(x−x1)=0 и оно дает два различных реальных корня x1 и x2, то Fn=axn1+bxn2 является решение. [Здесь a и b являются константами]

Случай 2 – Если это уравнение вычисляется как (x−x1)2=0, и оно порождает один действительный корень x1, то решением является Fn=axn1+bnxn1.

Случай 3 – Если уравнение дает два различных комплексных корня, x1 и x2 в полярной форме x1=r angle theta и x2=r angle(− theta), то Fn=rn(acos(n theta)+bsin(n theta)) является решением.

Проблема 1

Решите рекуррентное соотношение Fn=5Fn−1−6Fn−2, где F0=1 и F1=4.

Решение

Характеристическое уравнение рекуррентного соотношения –

x2−5x+6=0,

Итак, (x−3)(x−2)=0

Следовательно, корни –

x1=3 и x2=2

Корни реальны и различны. n $$

Проблема 2

Решите рекуррентное соотношение – Fn=10Fn−1−25Fn−2, где F0=3 и F1=17.

Решение

Характеристическое уравнение рекуррентного соотношения –

x2−10x−25=0

Итак, (x−5)2=0

Следовательно, существует один действительный корень x1=5

Поскольку существует единый действительный корень, он имеет вид случая 2

Следовательно, решение –

Fn=axn1+bnxn1

3=F0=a.50+b.0.50=a

17=F1=a.51+b.1.51=5a+5b

Решая эти два уравнения, мы получаем a=3 и b=2/5

Следовательно, окончательное решение – Fn=3.5n+(2/5).n.2n

Проблема 3

Решите рекуррентное соотношение Fn=2Fn−1−2Fn−2, где F0=1 и F1=3

Решение

Характеристическое уравнение рекуррентного соотношения –

x2−2x−2=0

Следовательно, корни –

x1=1+i и x2=1−i

В полярной форме,

x1=r angle theta и x2=r angle(− theta), где r= sqrt2 и theta= frac pi4

Корни воображаемые. Итак, это в форме случая 3.

Следовательно, решение –

Fn=( sqrt2)n(cos(n. Sqcap/4)+bsin(n. Sqcap/4))

1=F0=( sqrt2)0(acos(0. Sqcap/4)+bsin(0. Sqcap/4))=a

3=F1=( sqrt2)1(acos(1. Sqcap/4)+bsin(1. Sqcap/4))= sqrt2(a/ sqrt2+b/ sqrt2)

Решая эти два уравнения, мы получаем a=1 и b=2

Следовательно, окончательное решение –

Fn=( sqrt2)n(cos(n. Pi/4)+2sin(n. Pi/4))

Неоднородное рекуррентное соотношение и частные решения

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

Fn=AFn−1+BFn−2+f(n), где f(n) ne0

Связанное с ним однородное рекуррентное соотношение равно Fn=AFn–1+BFn−2

Решение (an) неоднородного рекуррентного отношения состоит из двух частей.

Первая часть – это решение (ah) связанного однородного рекуррентного соотношения, а вторая часть – это частное решение (at).

an=AH+at

Решение первой части выполняется с использованием процедур, описанных в предыдущем разделе.

Чтобы найти конкретное решение, мы находим подходящее пробное решение.

Пусть f(n)=cxn; пусть x2=Ax+B – характеристическое уравнение связанного однородного рекуррентного соотношения, а x1 и x2 – его корни.

Если x nex1 и x nex2, то at=Axn
Если x=x1, x nex2, то at=Anxn
Если x=x1=x2, то at=An2xn

Если x nex1 и x nex2, то at=Axn

Если x=x1, x nex2, то at=Anxn

Если x=x1=x2, то at=An2xn

пример

Пусть неоднородное рекуррентное соотношение имеет вид Fn=AFn–1+BFn−2+f(n) с характеристическими корнями x1=2 и x2=5. Пробные решения для различных возможных значений f(n) следующие:

е (п)	Пробные решения
4
5,2 ^н	An2 ⁿ
8,5 ⁿ	An5 ⁿ
4 ^н	A4 ^н
2n ² + 3n + 1	Ан ² + Бн + С

проблема

Решите рекуррентное соотношение Fn=3Fn−1+10Fn−2+7.

5n, где F0=4 и F1=3

Решение

Это линейное неоднородное отношение, где ассоциированное однородное уравнение имеет вид Fn=3Fn−1+10Fn−2 и f(n)=7,5n.

Характеристическое уравнение его связанного однородного отношения –

x2−3x−10=0

Или (x−5)(x+2)=0

Или x1=5 и x2=−2

Следовательно, ah=a.5n+b.(−2)n, где a и b – постоянные.

Поскольку f(n)=7,5n, то есть в форме cxn, разумным пробным решением at будет Anxn.

at=Anxn=An5n

После помещения решения в рекуррентное соотношение мы получаем –

An5n=3A(n−1)5n−1+10A(n−2)5n−2+7,5n

Разделив обе стороны на 5n−2, получим

An52=3A(n−1)5+10A(n−2)50+7,52

Или 25An=15An−15A+10An−20A+175

Или 35 =175

Или A=5

Итак, Fn=An5n=5n5n=n5n+1

Решение рекуррентного отношения можно записать в виде –

Fn=ah+at

=А.5п+Ь.(−2)п+n5п+1

Положив значения F0=4 и F1=3, в приведенном выше уравнении получим a=−2 и b=6

Следовательно, решение –

Fn=n5n+1+6. (−2)n−2,5n

Генерация функций

Генерирующие функции представляют последовательности, где каждый член последовательности выражается в виде коэффициента переменной x в формальном степенном ряду.

Математически, для бесконечной последовательности, скажем, a0,a1,a2, dots,ak, dots, производящая функция будет –

Gx=a0+a1x+a2x2+ dots+akxk+ dots= sum inftyk=0akxk

Некоторые области применения

Генерирующие функции могут быть использованы для следующих целей –

Для решения различных задач подсчета. Например, количество способов внести изменения для рупий. 100 примечание с примечаниями достоинств Rs.1, Rs.2, Rs.5, Rs.10, Rs.20 и Rs.50
Для решения рекуррентных отношений
Для доказательства некоторых комбинаторных тождеств
Для нахождения асимптотических формул для членов последовательностей

Для решения различных задач подсчета. Например, количество способов внести изменения для рупий. 100 примечание с примечаниями достоинств Rs.1, Rs.2, Rs.5, Rs.10, Rs.20 и Rs.50

Для решения рекуррентных отношений

Для доказательства некоторых комбинаторных тождеств

Для нахождения асимптотических формул для членов последовательностей

Проблема 1

Каковы производящие функции для последовательностей lbraceak rbrace с ak=2 и ak=3k?

Решение

Когда ak=2, производящая функция, G(x)= sum inftyk=02xk=2+2x+2×2+2×3+ точки

Когда ak=3k,G(x)= sum inftyk=03kxk=0+3x+6×2+9×3+ dots точки

Проблема 2

Что является производящей функцией бесконечного ряда; 1,1,1,1, dots?

Решение

Здесь ak=1 для 0 lek le infty

Следовательно, G(x)=1+x+x2+x3+ dots dots= frac1(1−x)

Для ak=ak,G(x)= sum inftyk=0akxk=1+ax+a2x2+ dots dots dots=1/(1−топор)

Для ak=(k+1)G(x)= sum inftyk=0(k+1)xk=1+2x+3×2 dots dots dots= frac1(1−x)2

Для ak=cnk,G(x)= sum inftyk=0cnkxk=1+cn1x+cn2x2+ dots dots dots+x2=(1+x)n

Для ak= frac1k!,G(x)= sum inftyk=0 fracxkk!=1+x+ fracx22!+ fracx33! dots dots dots=ex

13.

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

Рассмотрим последовательность элементов , первые элементов которой известны.

Всякую конечную последовательность элементов можно рассматривать как бесконечную, считая все её элементы, начиная с некоторого номера, равными нулю.

Определение. Рекуррентным соотношением между элементами последовательности называется формула вида ,.

Например, рекуррентное соотношение , , задает Последовательность чисел Фибоначчи: 1, 1, 2, 3, 5, 8,…

Для вычисления любого элемента последовательности с помощью заданного рекуррентного соотношения требуется вычисление всех предыдущих её элементов. Если заданная последовательность элементов удовлетворяет линейному рекуррентному соотношению, то решение задачи об отыскании общей формулы вычисления аналогично решению линейных дифференциальных уравнений высших порядков с постоянными коэффициентами.

Рассмотрим последовательность элементов . — известные начальные значения последовательности элементов, удовлетворяющих линейному неоднородному рекуррентному соотношению (1):

, (1)

— известные действительные числа.

Тогда (2) – линейное однородное рекуррентное соотношение, соответствующее (1):

. (2)

Определение. Характеристическим Уравнением, соответствующим (2), называется уравнение вида

. (3)

Корни уравнения (3) называются характеристическими числами рекуррентного соотношения (1).

Теорема 13.1. (О структуре общего решения линейного неоднородного рекуррентного соотношения (1)). Пусть общее решение линейного однородного рекуррентного соотношения (2), — Любое частное решение линейного неоднородного рекуррентного соотношения (1). Тогда — общее решение линейного неоднородного рекуррентного соотношения (1).

Теорема 13.2

. (О структуре общего решения линейного однородного рекуррентного соотношения (2)). Если — действительный корень характеристического уравнения (3) кратности , то общее решение линейного однородного рекуррентного соотношения (2) вычисляется по формуле , где — многочлен степени по переменной N, .

Коэффициенты определяются из начальных значений рекуррентного соотношения.

Общее решение рекуррентного соотношения (2) при и действительных корнях уравнения (3) и имеет вид

при ,

при =.

Пример. Выведем формулу Бине для вычисления последовательности чисел Фибоначчи.

Решение. ,

— линейное однородное рекуррентное соотношение с постоянными коэффициентами , начальные значения , .

Составим характеристическое уравнение и найдем характеристические числа и . Характеристическое уравнение имеет два различных корня кратности 1, значит, . Тогда общее решение , где и произвольные постоянные (, ). Используем заданные значения , составим систему из двух уравнений с двумя неизвестными:

Решением системы является пара чисел и . Таким образом, .□

Полученная формула называется формулой Бине и применяется для вычисления значений последовательности Фибоначчи только по их номеру, независимо от предыдущих членов последовательности.

Замечание. Часто рассматривается последовательность .

Например, для последовательности чисел Фибоначчи 0, 1, 1, 2, 3, 5, … рекуррентное соотношение записывается в виде , .

Задачи и упражнения.

13.1. Найдите формулу общего члена последовательности чисел, заданной рекуррентным соотношением , . Вычислите с помощью рекуррентного соотношения и по общей формуле.

13.2. Найдите формулу общего члена последовательности чисел, заданной рекуррентным соотношением , . Вычислите с помощью рекуррентного соотношения и по общей формуле.

13.3. Составьте рекуррентное соотношение последовательности квадратов натуральных чисел.

14. Понятие производящей функции.

Рассмотрим последовательность чисел

. (1)

Рассмотрим также последовательность функций действительной или комплексной переменной

. (2)

Формально составим функциональный ряд, используя элементы (1) и (2):

. (3)

Будем считать ряд (3) сходящимся абсолютно на Или в некоторой области комплексной плоскости. Функция Является суммой ряда (3).

Определение. Сумма ряда (3) называется Производящей функцией для заданной последовательности чисел (1) по заданной последовательности функций (2).

Чаще других используются степенные функции Или . Поэтому ряд (3), как правило, является степенным.

Например. Положим в формуле бинома Ньютона . Тогда

. Значит, функция является производящей функцией для последовательности биномиальных коэффициентов по системе степенных функций .

Пример. Составить производящую функцию последовательности чисел Фибоначчи , , .

Решение. Используем последовательность функций действительной переменной Умножим рекуррентное соотношение на и просуммируем по :

. (4)

По допущению все ряды абсолютно сходятся на R.

Подставив суммы в (4), получим , тогда .□

Задачи и упражнения.

14.1. Докажите, что функция является производящей для последовательности числе, общий член которой имеет вид .

14.2. Найдите производящую функцию для последовательности чисел .

14.3. Найдите общий член последовательности, для которой функция является производящей.

14.4. Найдите общий член последовательности, для которой функция является производящей.

< Предыдущая

Решение рекуррентных соотношений

\(\def\d{\displaystyle} \def\курс{Математика 228} \ новая команда {\ f} [1] {\ mathfrak # 1} \ новая команда {\ s} [1] {\ mathscr # 1} \def\N{\mathbb N} \def\B{\mathbf{B}} \def\circleA{(-.5,0) круг (1)} \ деф \ Z {\ mathbb Z} \def\circleAlabel{(-1.5,.6) узел[выше]{$A$}} \def\Q{\mathbb Q} \def\circleB{(.5,0) круг (1)} \def\R{\mathbb R} \def\circleBlabel{(1.5,.6) узел[выше]{$B$}} \def\C{\mathbb C} \def\circleC{(0,-1) круг (1)} \def\F{\mathbb F} \def\circleClabel{(.5,-2) узел[справа]{$C$}} \def\А{\mathbb А} \def\twosetbox{(-2,-1.5) прямоугольник (2,1.5)} \ деф \ Х {\ mathbb Х} \def\threesetbox{(-2,-2. {-1}} \def\nrml{\triangleleft} \ деф \ ст {:} \ деф \ ~ {\ широкая тильда} \def\rem{\mathcal R} \def\sigalg{$\sigma$-алгебра } \def\Гал{\mbox{Гал}} \def\iff{\leftrightarrow} \def\If{\Leftrightarrow} \ деф \ земля {\ клин} \def\И{\bigwedge} \защита\вход{\вход} \def\AAnd{\d\bigwedge\mkern-18mu\bigwedge} \def\Ви{\bigvee} \def\VVee{\d\Vee\mkern-18mu\Vee} \ деф \ имп {\ стрелка вправо} \def\Imp{\Rightarrow} \def\Fi{\Leftarrow} \def\var{\mbox{var}} \def\Th{\mbox{Th}} \защита\вход{\вход} \def\sat{\mbox{Sat}} \def\con{\mbox{Con}} \def\iffmodels{\bmodels\models} \def\dbland{\bigwedge \!\!\bigwedge} \def\дом{\mbox{дом}} \def\rng{\mbox{диапазон}} \def\isom{\cong} \DeclareMathOperator{\wgt}{wgt} \newcommand{\vtx}[2]{узел[заливка,круг,внутренний интервал=0pt, минимальный размер=4pt,метка=#1:#2]{}} \ новая команда {\ va} [1] {\ vtx {выше} {# 1}} \ новая команда {\ vb} [1] {\ vtx {ниже} {# 1}} \ новая команда {\ vr} [1] {\ vtx {право} {# 1}} \ новая команда {\ vl} [1] {\ vtx {слева} {# 1}} \renewcommand{\v}{\vtx{выше}{}} \def\circleA{(-. 5,0) круг (1)} \def\circleAlabel{(-1.5,.6) узел[выше]{$A$}} \def\circleB{(.5,0) круг (1)} \def\circleBlabel{(1.5,.6) узел[выше]{$B$}} \def\circleC{(0,-1) круг (1)} \def\circleClabel{(.5,-2) узел[справа]{$C$}} \def\twosetbox{(-2,-1.4) прямоугольник (2,1.4)} \def\threesetbox{(-2.5,-2.4) прямоугольник (2.5,1.4)} \def\ansfilename{практика-ответы} \def\shadowprops{{fill=black!50,shadow xshift=0.5ex,shadow yshift=0.5ex,path fading={круг с размытым краем 10 процентов}}} \ новая команда {\ hexbox} [3] { \def\x{-cos{30}*\r*#1+cos{30}*#2*\r*2} \def\y{-\r*#1-sin{30}*\r*#1} \рисовать (\х,\у) +(90:\r) — +(30:\r) — +(-30:\r) — +(-90:\r) — +(-150:\r) — +(150: \r) — цикл; \draw (\x,\y) узел{#3}; } \renewcommand{\bar}{\overline} \newcommand{\card}[1]{\left| #1 \справа|} \newcommand{\twoline}[2]{\begin{pmatrix}#1 \\ #2 \end{pmatrix}} \новая команда{\lt}{<} \новая команда{\gt}{>} \newcommand{\amp}{&} \)

Расследуй!21

Рассмотрим рекуррентное соотношение

\begin{уравнение*} а_п = 5а_{п-1} — 6а_{п-2}.

\end{уравнение*}

Какая последовательность получится, если начальные условия $a_0 = 1\text{,}$ $a_1 = 2\text{?}$ Приведите замкнутую формулу для этой последовательности.
Какую последовательность вы получите, если начальные условия $a_0 = 1\text{,}$ $a_1 = 3\text{?}$ Приведите замкнутую формулу.
Что если $a_0 = 2$ и $a_1 = 5\text{?}$ Найдите замкнутую формулу.

Мы видели, что часто легче найти рекурсивные определения, чем замкнутые формулы. К счастью для нас, есть несколько методов преобразования рекурсивных определений в закрытые формулы. Это называется решением рекуррентного соотношения . Напомним, что рекуррентное отношение — это рекурсивное определение без начальных условий. Например, рекуррентное соотношение для последовательности Фибоначчи имеет вид $F_n = F_{n-1} + F_{n-2}\text{.}$ (это вместе с начальными условиями $F_0 = 0$ и $F_1 = 1$ дать полное рекурсивное определение для последовательности. )

Пример 2.4.1

Найти рекуррентное соотношение и начальные условия для $1, 5, 17, 53, 161, 485\ldots\text{.}$

Решение

Нахождение рекуррентного отношения было бы проще, если бы у нас был некоторый контекст для проблемы (например, Ханойская башня). Увы, у нас есть только последовательность. Помните, что рекуррентное отношение говорит вам, как перейти от предыдущих терминов к будущим терминам. Что здесь происходит? Мы могли бы посмотреть на различия между терминами: $4, 12, 36, 108, \ldots\text{.}$ Обратите внимание, что они увеличиваются в 3 раза. Является ли исходная последовательность такой же? $1\cdot 3 = 3\text{,}$ $5 \cdot 3 = 15\text{,}$ $17 \cdot 3 = 51$ и так далее. Похоже, что мы всегда получаем на 2 меньше, чем следующий член. Ага!

Таким образом, $a_n = 3a_{n-1} + 2$ — это наше рекуррентное соотношение, а начальное условие — $a_0 = 1\text{.}$

Мы попробуем решить этих рекуррентные отношения. Под этим мы подразумеваем что-то очень похожее на решение дифференциальных уравнений: мы хотим найти функцию $n$ (замкнутая формула), которая удовлетворяет рекуррентному соотношению, а также начальному условию. ² Рекуррентные соотношения иногда называют разностными уравнениями, поскольку они могут описывать разницу между терминами, и это еще больше подчеркивает связь с дифференциальными уравнениями. Как и в случае с дифференциальными уравнениями, найти решение может быть сложно, но проверить правильность решения легко. 9п +1\\ \амп = а_н. \конец{выравнивание*}

Вот что говорит наше рекуррентное соотношение! У нас есть решение.

Иногда мы можем быть умнее и решить рекуррентное соотношение путем проверки. Мы генерируем последовательность, используя рекуррентное отношение, и отслеживаем, что мы делаем, чтобы увидеть, как перейти к нахождению только термина $a_n$. Вот два примера того, как вы можете это сделать.

Телескопирование относится к явлению, когда многие члены в большой сумме сокращаются, поэтому сумма «телескопируется». Например:

\begin{уравнение*} (2 — 1) + (3 — 2) + (4 — 3) + \cdots + (100 — 99) + (101 — 100) = -1 + 101 \end{уравнение*}

, потому что каждый третий член выглядит так: $2 + -2 = 0\text{,}$, а затем $3 + -3 = 0$ и так далее.

Мы можем использовать это поведение для решения рекуррентных соотношений. Вот пример.

Пример 2.4.3

Решить рекуррентное соотношение $a_n = a_{n-1} + n$ с начальным членом $a_0 = 4\text{.}$

Решение

Чтобы почувствовать рекуррентное соотношение, запишите первые несколько членов последовательности: $4, 5, 7, 10, 14, 19, \ldots\text{.}$ Посмотрите на разницу между терминами. $a_1 — a_0 = 1$ и $a_2 — a_1 = 2$ и так далее. Ключевым моментом здесь является то, что разница между термами равна $n\text{.}$ Мы можем записать это явно: $a_n — a_{n-1} = n\text{.}$ Конечно, мы мог бы прийти к этому выводу непосредственно из рекуррентного соотношения, вычитая $a_{n-1}$ с обеих сторон.

Теперь используйте это уравнение снова и снова, каждый раз меняя $n$:

\начать{выравнивать*} а_1 — а_0 \амп = 1\\ а_2 — а_1 \амп = 2\\ а_3 — а_2 \амп = 3\\ \vdots\quad\усилитель\quad\vdots\\ a_n — a_{n-1} \amp = n. \конец{выравнивание*}

Сложите все эти уравнения вместе. В правой части мы получаем сумму $1 + 2 + 3 + \cdots + n\text{.}$ Мы уже знаем, что это можно упростить до $\frac{n(n+1)} {2}\text{.}$ Что происходит с левой стороны? Получаем

\begin{уравнение*} (a_1 — a_0) + (a_2 — a_1) + (a_3 — a_2) + \cdots (a_{n-1} — a_{n-2})+ (a_n — a_{n-1}). \end{уравнение*}

Это сумма телескопов. У нас остались только $-a_0$ из первого уравнения и $a_n$ из последнего уравнения. Собрав все вместе, мы получим $-a_0 + a_n = \frac{n(n+1)}{2}$ или $a_n = \frac{n(n+1)}{2} + a_0\text {.}$ Но мы знаем, что $a_0 = 4\text{.}$ Таким образом, решение рекуррентного соотношения с учетом начального условия равно 9n f(k)\text{,}\), поэтому нам нужно знать замкнутую формулу для этой суммы.

Однако телескопирование не поможет нам с рекурсией, такой как $a_n = 3a_{n-1} + 2$, поскольку левая часть не будет телескопироваться. У вас будет $-3a_{n-1}$ , но только один $a_{n-1}\text{.}$ Однако мы все еще можем быть умнее, если используем итерацию .

Мы уже видели пример итерации, когда нашли замкнутую формулу для арифметической и геометрической последовательностей. Идея в том, что мы повторим процесс нахождения следующего члена, начиная с известного начального условия, пока не получим $a_n\text{.}$ Затем упростим. В примере с арифметической последовательностью мы упростили, умножив $d$ на количество раз, которое мы добавляем к $a$, когда мы получаем $a_n\text{,}$, чтобы получить из $a_n = a + d + d + d + \cdots + d$ до $a_n = a + dn\text{.}$

Чтобы увидеть, как это работает, давайте рассмотрим тот же пример, который мы использовали для телескопирования, но на этот раз используем итерацию.

Пример 2.4.

Использовать итерацию для решения рекуррентного соотношения $a_n = a_{n-1} + n$ с $a_0 = 4\text{.}$

Решение

Снова начните с записи рекуррентного соотношения, когда $n = 1\text{.}$ На этот раз не вычитайте члены $a_{n-1}$ с другой стороны:

\begin{уравнение*} а_1 = а_0 + 1. \end{уравнение*}

Теперь $a_2 = a_1 + 2\text{,}$, но мы знаем, что такое $a_1$. Подстановкой получаем

\begin{уравнение*} а_2 = (а_0 + 1) + 2. \end{уравнение*}

Теперь перейдите к $a_3 = a_2 + 3\text{,}$, используя наше известное значение $a_2\text{:}$

\begin{уравнение*} а_3 = ((а_0 + 1) + 2) + 3. \end{уравнение*}

Мы замечаем закономерность. Каждый раз мы берем предыдущий член и добавляем текущий индекс. Итак,

\begin{уравнение*} a_n = ((((a_0 + 1) +2)+3)+\cdots + n-1) + n. \end{уравнение*}

Перегруппировав термины, мы замечаем, что $a_n$ это просто $a_0$ плюс сумма целых чисел от $1$ до $n\text{.}$ Итак, поскольку $a_0 = 4\текст{,}$

\begin{уравнение*} a_n = 4 + \frac{n(n+1)}{2}. \end{уравнение*}

Конечно, в этом случае нам еще нужно было знать формулу суммы $1,\ldots,n\text{.}$ Попробуем выполнить итерацию с последовательностью, для которой телескопирование не работает.

Пример 2.4.5

Решить рекуррентное соотношение $a_n = 3a_{n-1} + 2$ при условии $a_0 = 1\text{.}$

Решение

Снова повторяем рекуррентное отношение, достраивая до индекса $n\text{.}$

\начать{выравнивать*} а_1 \амп = 3а_0 + 2\\ а_2 \амп = 3(а_1) + 2 = 3(3а_0 + 2) + 2\\ а_3 \amp = 3[а_2] + 2 = 3[3(3а_0 + 2) + 2] + 2\\ \vdots \amp \qquad \vdots \qquad \qquad \vdots\\ a_n \amp = 3(a_{n-1}) + 2 = 3(3(3(3\cdots(3a_0 + 2) + 2) + 2)\cdots + 2)+ 2. {n-2} + \cdots + 2\cdot 3 + 2. \конец{выравнивание*} 9н — 1. \end{уравнение*}

Итерация может быть запутанной, но когда рекуррентное отношение ссылается только на один предыдущий термин (и, возможно, на некоторую функцию от $n$) оно может работать хорошо. Однако попытка повторения рекуррентного отношения, такого как $a_n = 2 a_{n-1} + 3 a_{n-2}$, будет слишком сложной. Нам потребуется отслеживать два набора предыдущих терминов, каждый из которых выражается двумя предыдущими терминами, и так далее. Длина формулы будет расти экспоненциально (фактически удваиваться каждый раз). К счастью, существует метод решения рекуррентных соотношений, который очень хорошо работает с такими отношениями.

ПодразделТехника характерного корня

Предположим, мы хотим решить рекуррентное отношение, выраженное в виде комбинации двух предыдущих терминов, например $a_n = a_{n-1} + 6a_{n-2}\text{.}$ Другими словами, мы хотим найти функцию $n$, которая удовлетворяет \(a_n — a_{n-1} — 6a_{n-2} = 0\text{. 2 + \ альфа х + \ бета \end{уравнение*} 9н. \end{уравнение*}

Возможно, наиболее известным рекуррентным соотношением является $F_n = F_{n-1} + F_{n-2}\text{,}$, которое вместе с начальными условиями $F_0 = 0$ и $F_1 = 1$ определяет последовательность Фибоначчи. Но заметьте, что это именно тот тип рекуррентного отношения, для которого мы можем использовать метод характеристического корня. Когда вы это сделаете, единственное, что изменится, это то, что характеристическое уравнение не учитывается, поэтому вам нужно использовать квадратичную формулу, чтобы найти характеристические корни. Фактически, это дает третье самое известное иррациональное число, $\varphi\text{,}$ золотое сечение .

Прежде чем оставить метод характеристического корня, следует подумать о том, что может произойти при решении характеристического уравнения. У нас есть пример выше, в котором характеристический многочлен имеет два различных корня. Эти корни могут быть целыми или, возможно, иррациональными числами (для их нахождения требуется квадратичная формула). n\text{.}\) Нам повезло: 9п\), если было 3 различных корня). Также возможно решить рекуррентные соотношения вида $a_n = \alpha a_{n-1} + \beta a_{n-2} + C$ для некоторой константы $C\text{.}$ также возможно (и приемлемо), чтобы характеристические корни были комплексными числами.

ПодразделУпражнения

1

Найдите следующие два термина в $(a_n)_{n\ge 0}$ начиная с $3, 5, 11, 21, 43, 85\ldots.\text{.}$ Затем дайте рекурсивное определение для последовательности. Наконец, используйте метод характеристического корня, чтобы найти замкнутую формулу для последовательности. 9п\текст{.}\)

5

Найдите решение рекуррентного соотношения $a_n = 3a_{n-1} + 4a_{n-2}$ с начальными условиями $a_0 = 5$ и $a_1 = 8\text{.}$

6

Решить рекуррентное соотношение $a_n = 2a_{n-1} — a_{n-2}\text{.}$

Каково решение, если начальные условия равны $a_0 = 1$ и $a_1 = 2\text{?}$
Какими должны быть начальные условия для $a_9 = 30\text{?}$
Для которых $x$ существуют начальные члены, которые делают $a_9n$ также является решением рекуррентного соотношения для любых констант $c, d\text{. }$
9
Вспомните волшебный автомат по производству конфет в ближайшем продуктовом магазине. Предположим, что в первый раз, когда в машину кладут четвертак, выходит 1 кегля. Во второй раз 4 кегли, в третий раз 16 кеглей, в четвертый раз 64 кегли и т.д.
1. Найдите как рекурсивную, так и замкнутую формулу для определения того, сколько Skittles получит n -й клиент.
2. Проверьте свое решение на замкнутую формулу, решая рекуррентное соотношение с помощью метода характеристического корня.
10
У вас есть доступ к $1\times 1$ плиткам 2 разных цветов и $1\times 2$ плиткам 3 разных цветов. Мы хотим выяснить, сколько различных $1 \times n$ схем пути мы можем составить из этих плиток.
1. Найти рекурсивное определение последовательности $a_n$ путей длины $n\text{.}$
2. Решите рекуррентное соотношение, используя метод характеристического корня.
11
Пусть $a_n$ будет количеством $1 \times n$ плиток, которые вы можете сделать, используя $1 \times 1$ квадратов, доступных в 4 цветах, и $1 \times 2$ домино, доступных в 5 цветов.
1. Сначала найдите рекуррентное отношение для описания проблемы. Объясните, почему рекуррентное соотношение верно (в контексте задачи).
2. Запишите первые 6 членов последовательности $a_1, a_2, \ldots\text{.}$
3. Решить рекуррентное соотношение. То есть найти замкнутую формулу для $a_n\text{.}$
12
Рассмотрим рекуррентное соотношение $a_n = 4a_{n-1} — 4a_{n-2}\text{.}$
1. Найдите общее решение рекуррентного соотношения (остерегайтесь повторяющегося корня).
2. Найдите решение, когда $a_0 = 1$ и $a_1 = 2\text{.}$
3. Найдите решение, когда $a_0 = 1$ и $a_1 = 8\text{.}$
Лекция 18. Рекуррентные соотношения
Лекция 18. Рекуррентные соотношения
Примечание: на этой странице используются следующие специальные символы: греческая заглавная буква тета: (Θ), Греческая заглавная буква омега (Ω), знак минус (-). Если эти символы отображаются неправильно, ваш браузер не может полностью обрабатывать HTML 4.0, и часть следующего текста, вероятно, будет иметь неправильный вид.
Асимптотическая сложность имеет ограничения, но она по-прежнему является полезным инструментом анализа и повышение производительности программы. Использование нотации big-O упрощает задача анализа производительности. Для OCaml мы предполагаем, что все редукции выполняемые во время оценки, занимают постоянное время, включая все арифметические операции и сопоставление с образцом.
Это предположение может показаться неожиданным, если вы подумаете о работе замещения, которую по-видимому, требуется замещающей моделью оценки: переменная может появляться в разных местах кода. Реализация OCaml избегает работы по замене, вместо этого отслеживание всех включенных в область замен в отдельном окружающая среда это позволяет искать переменные, когда нужны их привязки.
Следующая процедура умножения не очень эффективна:
```
(* Возвращает: умножить на 1 a b равно a*b. 
   Требуется: б ≥ 0 *)
пусть раз1 (a:int) (b:int) :int =
  если (b = 0), то 0 иначе a + times1(a,b-1) 
```
Каков порядок роста требуемого времени в раз1 как функция n , где n – величина параметра b ? Обратите внимание, что «размер» числа может быть измерен либо с точки зрения его величины или с точки зрения количества цифр (место, необходимое для записи номер вниз). Часто используется количество цифр, но здесь мы используем величину. Обратите внимание, что для записи число величины x , таким образом, эти две меры очень разные.
Мы предполагаем, что все примитивные операции в функции ×1 ( , если , + , = и - ) и накладные расходы для функции звонки занимают постоянное время. Таким образом, если n =0, подпрограмма занимает не более некоторого постоянного времени c ₁ . Если n >0, время, затраченное на ввод величины n не более чем некоторая константа c ₂ , плюс время, затраченное на рекурсивный вызов n - 1 . Другими словами, существуют константы с ₁ и c ₂ такие что T ( n ) удовлетворяет
Т ( н ) = Т ( н - 1 ) + с ₁ для n > 0
Т (0) = с ₂
Это рекуррентное соотношение (или просто повторение определение функции T(n). Просто говорится, что время умножить число a на другое число b размера n > 0 это время, необходимое для умножения на на число размером n - 1 плюс a постоянный объем работы (выполняемых примитивных операций).
Рекуррентное соотношение является индуктивным определением функции. Это конкретное рекуррентное соотношение имеет уникальное закрытый раствор который определяет T(n) без какой-либо рекурсии:
T ( n ) = c ₂ + c ₁ n
, что равно O ( n ), поэтому алгоритм является линейным по величине b . Это уравнение можно получить, обобщая малые значения n , затем докажите, что это действительно решение рекуррентного соотношения индукцией по n .
Теперь рассмотрим следующую процедуру умножения двух чисел:
```
  весело  раз2(a:int, b:int):int =
      если  (b = 0)  то 
      0
      иначе   если  четное(b)  то 
      раз2 (двойной (а), половинный (б))
      еще 
      а + раз2(а, б-1) 
```
Опять нам нужно выражение для времени работы через n , величина параметра b . Мы предполагаем, что двойное и половинное операции являются постоянным временем (это можно было бы сделать за постоянное время, используя арифметический сдвиг), а также стандартные примитивы. Рекуррентное соотношение ибо эта задача сложнее предыдущей:
Т(n) = T(n-1) + с ₁ , если n > 0 и n нечетно
Т(n) = T(n/2) + с ₂ , если n > 0 и n четно
T(0) = c ₃
Нам как-то нужно выяснить, как часто первая и вторая ветви будет взято это рекуррентное соотношение. Легко, если n является степенью двойки, т.е. если n = 2 ^м для некоторого целого числа м . В этом случае вторая ветвь будет взято только тогда, когда n = 1, потому что 2 ^m четно за исключением случаев, когда м = 0, т. е. когда n = 1. Отметим далее, что T(1) = O(1) , потому что T(1) = T(0) + O(1) = O(1) + O(1) = O(1) . Таким образом, для этого частном случае мы получаем рекуррентное соотношение:
Т(n) = T(n/2) + с ₂ , если n > 0 и n является степенью числа 2
Т(0) = с ₃
или
Т(n) = T(n/2) + с ₂ для n > 0 и n является степенью числа 2
Т(0) = с ₃
для некоторых констант c ₂ и c ₃ . Для полномочий 2, решение в закрытой форме:
T(n) = c ₃ + c ₂ log ₂ n
, что равно O(log n) .
Что, если n не является степенью числа 2? Время работы по-прежнему O(log n) даже в этом более общем случае. Интуитивно это потому, что если n странный, тогда n - 1 четно, поэтому при следующем рекурсивном вызове ввод будет уменьшен вдвое. Таким образом, ввод уменьшается вдвое по крайней мере один раз в каждых двух рекурсивных вызовах, т. е. все, что вам нужно, чтобы получить O (log n) .
Хорошим способом формальной обработки этого является взимание платы со стоимости звонка на раз2 на нечетном входе стоимость рекурсивного вызова на четном входе, который должен быть немедленно следуйте за ним . Рассуждаем так: на четном входе n , стоимость указана стоимость рекурсивного вызова n/2 плюс константа или
Т(n) = T(n/2) + с ₂
как раньше. На нечетном входе n мы рекурсивно вызываем процедуру на n-1 , что является четным, поэтому мы немедленно снова вызываем процедуру на (n-1)/2 . Таким образом, общая стоимость нечетного ввода равна стоимости рекурсивного вызова (n-1)/2 . плюс константа. В этом случае мы получаем
T(n) = T((n-1)/2) + с ₁ + с ₂
В любом случае
T(n) ≤ T(n/2) + (c ₁ + c ₂ )
, решение которого по-прежнему равно O(log n) . Такой подход более-менее то же, что и явная раскрутка предложения else , которое обрабатывает нечетные входные данные:
```
  весело  раз2(a:int, b:int):int =
      если  (b = 0)  тогда 
      0
      иначе   если  четное(b)  то 
      раз2 (двойной (а), половинный (б))
      еще 
      а + раз2 (двойной (а), половинный (б-1)) 
```
затем анализирует переписанную программу, фактически не переписывая.
Начисление одной операции на другую (ограничение количества раз, когда одна вещь может происходит по количеству раз, когда происходит что-то другое) является распространенным методом для анализа времени работы сложных алгоритмов.
Обозначение ордеров является полезным инструментом, и его не следует рассматривать как просто теоретическое упражнение. Например, практическая разница во времени работы между логарифмическим ×1 и линейным ×2 есть заметно даже при умеренных значениях n .
Ключевыми моментами являются:
- Мы можем использовать асимптотические скорости роста функций (поскольку n получает большой) для ограничения ресурсов, требуемых данным алгоритмом, и для сравнения относительная эффективность различных алгоритмов.
- Нотация Big-O обеспечивает способ выражения приблизительных границ ресурсов. требуется в форме, которая имеет смысл, но с которой легко работать.
- Рекуррентные отношения можно использовать для выражения времени выполнения рекурсивных программы, и часто может быть решена для выражения в закрытой форме Продолжительность.
Давайте рассмотрим полезный алгоритм более подробно и покажем, что он не только правильно, но и то, что его производительность в наихудшем случае составляет O ( n LG n ). Мы рассмотрим алгоритм сортировки слиянием , рекурсивный алгоритм для сортировка списка элементов. Сортировка слиянием — это пример «разделяй и властвуй» . алгоритм. Он сортирует список, рекурсивно разделяя его на два меньших подсписка. сортировка подсписков, а затем объединение двух отсортированных списков вместе для получения окончательный результат. Объединение двух списков довольно просто, если они сами уже отсортированы. Чтобы доказать правильность и время выполнения сортировки слиянием, нам понадобится более сильный техника доказательства: сильная индукция , также называемая курсом ценностей индукция.
Сильная индукция
Сильная индукция имеет те же шаги, что и обычная индукция, но индукционная гипотеза немного другая:
1. Сформулируйте предложение, которое необходимо доказать в терминах P ( n )
2. Базовый вариант: показать P ( n ₀ ) правда
3. Гипотеза индукции: Предположим, что P ( м ) верно для всех n ₀ ≤ m ≤ n . Это отличается от обычной индукции, где мы можем только предположить, что P ( м ) верно для м = n .
4. Шаг индукции: Используя гипотезу индукции, докажите P ( n +1) правда.
5. Вывод: P ( n ) верно для все n ≥ n ₀
Мы можем формализовать этот процесс как правило вывода, которое дает нам способ доказать предложение ∀n.P(n) для некоторого предиката P. Вот правила для слабая (обычная) и сильная индукция соответственно:
Р(0) ∀n.P(n) ⇒ Р(n+1)
∀n.P(n)
(слабая индукция)
(∀n’.n’
∀n.P(n)
(сильная индукция)
Зачастую проще доказать границы асимптотической сложности, используя сильные индукции, чем при использовании обычной индукции, потому что у вас более сильный гипотеза индукции для работы: ∀n’. n’
Реализация и правильность сортировки слиянием
```
(* split(xs) — это пара (ys,zs), где половина (округление)
 * элементы xs находятся в ys, а остальные — в zs.
 *)
позвольте разделить (xs: список int): список int * список int =
    let loop (xs: список целых чисел, слева: список целых чисел, справа: список целых чисел)
            : целочисленный список * целочисленный список =
сопоставить xs с
[] -> (влево, вправо)
| [x] -> (x::влево, вправо)
| x::y::rest -> loop(rest, x::left, y::right)
    в
петля (xs, [], [])
(* Более простой способ записи разделения. Вспомним определение
   складной Какова асимптотическая производительность foldl f lst0
   lst, где f — функция O(1), а lst — n-элемент
   список? На). *)
забавный сплит'(xs:int list) : int list * int list =
  List.fold_left (fun (left,right) x -> (x::right,left)) ([],[]) xs

(* merge(left,right) — отсортированный список (в порядке возрастания)
 * содержащий все элементы слева и справа.
 * Требуется: слева и справа отсортированные списки *)
веселое слияние (слева: список целых чисел, справа: список целых чисел): список целых чисел =
  совпадать (слева, справа) с
    ([],_) -> вправо
  | (_,[]) -> влево
  | (x::left_tail, y::right_tail) ->
      (если x > y, то y::(merge(left, right_tail))
                иначе x::(слияние(left_tail, right))))
 
```
Откуда мы знаем, что объединяет ? Индукцией по сумме длина двух входных списков (т. е. длина(слева)+длина(справа) ). Ясно, что если эта минимальная длина равна нулю, функция работает, потому что один из используются первые два случая, и они тривиально правильны. Что насчет генерала дело? Мы пытаемся показать, что слияние работает со списками слева и справа общая длина которых n +1, и мы допускается предположить, что он работает на списках слева и справа общая длина которых n или меньше. Если один из два списка пусты, функция работает. Что делать, если оба списка не пусты? От предварительное условие ( требует пункта ) мы знаем, что x является наименьший элемент оставил и y наименьший элемент справа , а rest_left и rest_right являются отсортированными списками. Наша индуктивная гипотеза позволяет предположить, что объединяют работает правильно в рекурсивных вызовах, потому что общая длина двух списков меньше, чем общая длина левого и правого, и предварительное условие слияние в рекурсивных вызовах выполнено (применяется к отсортированным спискам). Если выполняется ветвь , затем , и должны быть меньше любого элемент в любом списке; следовательно, y::(merge(left, rest_right)) есть отсортированный список. И наоборот, в ветке else x меньше чем или равен любому элементу в любом списке; поэтому х::(слияние(остальное_лево, верно)) тоже отсортированный список. И мы видим, что сливаются с . не «теряет» никаких элементов слева или справа предполагая, что рекурсивные вызовы тоже не работают.
Теперь мы можем написать саму функцию сортировки слиянием. Обратите внимание, как мы явно отделить спецификацию функции от описания алгоритм, который его реализует. С объединить и разделить указано выше, нам не нужно даже такое подробное описание того, как слияние_сортировка работает.
```
(* merge_sort(xs) — это список, содержащий те же элементы, что и xs, но в
 * по возрастанию (не по убыванию) в порядке сортировки.  *)
пусть merge_sort (xs: список int) : список int =
(* Реализация: списки размера 0 или 1 уже отсортированы. В противном случае
 * разбить список на два списка одинакового размера, рекурсивно отсортировать
 * их, а затем объедините два списка вместе. *)
  сопоставить xs с
    ([]|[_]) -> хз
  | _ -> пусть (слева, справа) = разделить xs в
           слияние (сортировка слиянием (слева), сортировка слиянием (справа))
 
```
Опять же, по индукции по длине входного списка мы можем увидеть, что это функция работает. Для списков длины 0 или 1 это явно работает. Для больших списков мы обратите внимание на спецификацию для разделить , что оба оставили и правильно должны содержать некоторые элементы и вместе они содержат все элементы х . По индуктивной гипотезе merge_sort применение к каждому из этих списков приводит к отсортированным спискам. Из спецификации на слияние результатом должен быть отсортированный список, содержащий все элементы хз. Поэтому функция merge_sort будет работать правильно.
Асимптотический временной анализ сортировки слиянием
Теперь давайте покажем, что merge_sort не только правильный , но и также эффективный алгоритм для сортировки списков чисел. Мы начинаем с бездоказательно наблюдая, что производительность разделяет функцию линейна по размеру входного списка. Это можно показать с помощью того же подхода мы возьмем за слияние , поэтому давайте просто посмотрим на слияние вместо.
Функция слияния также является линейной по времени — то есть O ( n ) — в общей длине двух входных списков. Сначала найдем повторение отношение к времени выполнения. Предположим, что общая длина входных списков равна нулю или один. Тогда функция должна выполнить одно из двух O (1) руки падежного выражения. Это займет некоторое время c ₀ для выполнения. Итак, у нас есть
T (0) = c ₀
T (1) = c ₀
Теперь рассмотрим списки общей длины n . Рекурсивный вызов находится в списках общей длины n −1, так что у нас есть
Т ( н ) = Т ( н -1) + с ₁
, где c ₁ — постоянная верхняя время, необходимое для выполнения оператора if и оператора :: (что занимает постоянное время для обычных реализаций списков). Это дает нам рекуррентное соотношение для решения для T . Мы можем применить итерационный метод к решить рекуррентное соотношение, расширив неравенства рекуррентного отношения для первого несколько шагов.
T (0) = c ₀
T (1) = c ₀ T (2) = T (1) + c ₁ = c ₀ + c ₁ T (3) = T (2) + c ₁ = c ₀ + 2 c ₁ T (4) = T (3) + c ₁ = c ₀ + 3 c _{1
. ..} T ( n ) = T ( − 8 n 1 90 + с ₁ = с ₀ + ( н −1) в ₁ = ( с ₀ + с ₁ ) _{+ с ₁ н}
Мы замечаем закономерность, которую фиксирует последняя строка. Напомним, что Т ( n ) O ( n ) если для всех n больше некоторого n ₀ , мы можем найти константу k такую, что T ( и ) < кн . Для n не менее 1 этого легко добиться, установив k = с ₀ + 2 с ₁ . Или мы можем просто вспомнить что любой полином первой степени равен O ( n ) а также Θ( n ). Еще более простой способ найти правильную оценку состоит в том, чтобы заметить, что выбор константы c0 и c1 не имеют значения; если мы подставим 1 для них обоих, мы получим T (1) = 1, Т (2)=2, Т (3)=3, д. , что явно O ( n ).
Теперь давайте рассмотрим саму функцию merge_sort . Опять же, для нулевые и одноэлементные списки мы вычисляем за постоянное время. Для n -элемент списков мы делаем два рекурсивных вызова, но для подсписков, которые примерно вдвое меньше, и вызовы на разделяют и , объединяют , каждый из которых принимает Θ( n ) время. Для простоты будем считать, что подсписки ровно вдвое меньше. Полученное рекуррентное соотношение имеет следующий вид:
T (0) = C ₀
T (1) = C ₀ T (_{N 9075) =}). + c ₁ n + c ₂ n + c ₃
Давайте воспользуемся итеративным методом, чтобы определить время выполнения merge_sort . Мы знаем, что любое решение должно работать для произвольных констант с ₀ и c ₄ , значит опять их заменяем оба с 1, чтобы все было просто. Это оставляет нам следующее повторение уравнения для работы:
T (1) = 1
T ( n ) = 2 T ( n /2) + n
Начиная с итеративного метода, мы можем начать расширять уравнение времени пока не заметим закономерность:
Т ( N ) = 2 T ( N /2) + N
= 2 (2 T ( N /4) + N /2) + /4) + 0404040407. T ( n /4) + n + n
     = 4(2 T ( n /8) + n /4) + n + n
     = 8 T ( n /8) + n + n + n
     = нТл ( n / n ) + n + … + n + n + n
     = n + n + … + n + n + n
Подсчет количества повторений n в сумма в конце видим что есть lg n +1 их. Таким образом, время работы составляет n (lg n + 1) = n lg n + n . Мы обратите внимание, что n LG n + n < n lg n + n lg n = 2 n lg n для n >0, поэтому время работы равно O ( n LG N ). Итак, теперь мы провели анализ с помощью итеративного метод, давайте используем сильную индукцию, чтобы проверить правильность оценки.
Анализ сортировки слиянием с использованием сильной индукции
Свойство P(n) для доказательства:
n ≥ 1 ⇒ T ( n ) = n lg n + n
Доказательство сильной индукцией (курсом значений) по n . Для произвольного n , показать P(n) истинно, предполагая индукционная гипотеза T ( m ) = m lg m + m для всех m < n .
No related posts.