A2. Падаваны мастер теоремы

Баллы

Часть 1: 1 пункт = 1 балл

Часть 2: 1п = 1 балл, 2п = 2 балла

Часть 3: 1 пункт = 1.5 балла

Часть 1.

Оценить можно ли использовать Мастер-теорему для данных соотношений, если да, найти ассимптотически верхнюю границу сложности - 𝒪(g(n)). В обоих случаях привести обоснования

1. 𝘛(n)=13*𝘛(n/21)+n3/2

2. 𝘛(n)=𝘛(n-2)+𝘛(n-3)+n, 𝘛(1)=𝘛(2)=𝘛(3)=1 - вот эта последовательность(без синусов) называется последовательностью Padovan-а. Название взято по этим мотивам :D

3. 𝘛(n)= 12*𝘛(n/4)+n√(,n√(,n))

4. 𝘛(n)=2*𝘛(n/3)+2*𝘎(n/3)+𝒪(1)

   𝘎(n)=𝘎(n/3)+n*sin(n)

5. 𝘛(n)=9/4*𝘛(2/3*n)+n2*ln(√(,n))*ln(ln(n))

Решения

1. Условия мастер теоремы выполняются. a=13, b=21, c=3/2, ƒ(n)=1

   (log_b)(a)=(log_21)(13)<1, c=3/2>1⇒c>(log_b)(a)⇒𝘛(n)=𝒪(nc)=𝒪(n√(,n))

2. Условия мастер теоремы не выполняются. Подзадачи имеют разный размер.

3. Условия мастер теоремы выполняются. n√(,n√(,n))=n7/4⇒ƒ(n)=1.*a=12, b=4

   (log_b)(a)=(log_4)(12)=1+(log_4)(3) vs 7/4=1+3/4

   (log_4)(3)≌0.792>0.75 - проверяем что люди не забили на negligable разницу

   𝘛(n)=𝒪(n(log_b)(a))=𝒪(n1.792)

4. Условия мастер теоремы не выполняются. Можно заметить что функция n*sin(n) хоть и в целом растет, но каждый полупериод относительно sin(x)(через ровно π) меняет свой знак, а значит является чередующийся и такое соотношение нельзя проанализировать.

5. Условия мастер теоремы выполняются. a=9/4,b=3/2,c=2 ⇒

   ⇒ƒ(n)=ln(√(,n))*ln(ln(n)).

   Можно показать что ƒ(n) монотонно возрастает. Пытливые возьмут производную, ленивые прикрепят скрин из десмоса

   (log_b)(a)=(log_3/2)(9/4)=2=c⇒𝘛(n)=𝒪(nc*ƒ(n)*ln(n))

   =𝒪(n2*ln(n)*ln(√(,n))*ln(ln(n)))=𝒪(n2*ln2(n)*ln(ln(n)))

Часть 2.

Для тех реккурентных соотношений для которых не возможно установить границу сложности, опеределить границу сложности стандартными методами(метод подстановки или метод итерации)

2. 𝘛(n)=𝘛(n-2)+𝘛(n-3)+n

   Что бы найти полную оценку запишим характерестический многочлен функции 𝘛(n)

   ρx=ρ(x-2)+ρ(x-3)⇔ρ3=ρ1+1⇔ρ3-ρ-1=0

   Единственный действительный корень уравнения - пластическое число ρ≈1.3247 . Можно убетиться что длина радиус векторов двух других корней, по модулю меньше 1 (здесь можно привести численные значения из солвера или калькулятора), а значит при возведении в степень они будут уменьшать свой вклад, и ассимптотически доминировать в формуле общего члена реккуренты будет именно ρn. Поэтому воспользуемся методом подстановки следующим образом:

   𝘛(n)=𝒪(ρn*n)⇔𝘛(n)≤C⋅ρn*n

   𝘛(n)≤C*ρ(n-2)*(n-2)+C*ρ(n-3)*(n-3)+n≤C*ρ(n-2)*n+C*ρ(n-3)*n

   C*ρ(n-2)*n+C*ρ(n-3)*n≤C*ρn*n - переписали исходное утверждение

   ρ(n-2)*n+ρ(n-3)*n≤ρn*n

   ρ(n-2)+ρ(n-3)≤ρn

   Теперь зная что ρ - это корень данного уравнения, можно переписать левую часть:

   ρn≤ρn - верное неравенство начиная с какого-то (n_0)

4. 𝘛(n)=2*𝘛(n/3)+2*𝘎(n/3)+𝒪(1) и 𝘎(n)=𝘎(n/3)+n*sin(n)
   Легко сразу заметить что функция sin(n) ограничена сверху 1.Поэтому n*sin(n) можно ограничить n сверху. Получим что 𝘎(n)=𝘎(n/3)+𝒪(n)

   Так как функция не содержит в себе повтороного вызова то можно сначала раскрыть функцию 𝘛(n) полностью а после этого начать раскрывать функцию𝘎(n)

   𝘛(n)=2*𝘛(n/3)+2*𝘎(n/3)=4*𝘛(n/9)+2*𝘎(n/3)+4*𝘎(n/9)→

   →2(log_3)(n)+(∑_i=1^(log_3)(n))(2i*𝘎(n/(3i))). Обозначим за m=(log_3)(n). Теперь начнем раскрывать все 𝘎(n)

   2*𝘎(n/3)=2*(𝘎(n/9)+𝒪(n/3))

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

   (2+4)*𝘎(n/9)=(2+4)*(𝘎(n/27)+𝒪(n/9))

   ⋯

   (∑_j=1^i)(2j)⋅𝘎(n/(3i))=(∑_j=1^i)(2j)⋅(𝘎(n/(3(i+1)))+𝒪(n/(3i)))

   Последовательно раскрывая функции мы в пределе(n→m) мы получим следующее выражение

   𝘛(n)=2m+(∑_i=1^m)[(∑_j=1^i)(2j)⋅𝒪(n/(3i))]

   Наконец свернем вторую часть выражения. Что бы это сделать посмотрим на внешнюю сумму "горизонтально". Во всех слагаемых присутствуют о-шки с константой 2,в m- 1 слагаемом есть о-шки с константой 4.Продолжая эту логику проведем группирование этих компонент по доступной константе. Получим что:

   2*(n*(log_3)(n))

   4*(n/3*(log_3)(n/3))=4/3*(n*(log_3)(n)-1)

   8/9*(n*(log_3)(n)-2)

   ⋯

   (2/3)m*(n*(log_3)(n)-(log_3)(n))

   Теперь можно оценить сумму этих внутренних сумм сверху. Все к/ф перед внутренними суммами можно оценить сверху 2, а остаток который вычитается отбросить. Получим выражение:

   2m+2*m2*n

   Итоговая оценка: 𝘛(n)=𝒪(2(log_3)(n)+n*(log_3)2(n))

Часть 3.

Теория про Аккра-Баззи

Ссылка на док-во для интересующихся - тык

Для следующих соотношений попытайтесь вычислить оценку сначала при помощи мастер теоремы, а за тем при помощи ее обобщения - Метода Аккра-Баззи. Получилась ли разница в оценках? Ответ обоснуйте

1.*𝘛(n)=𝘛(n/4)+2*𝘛(n/16)+n*(log_2)(n)

2.*𝘛(n)=3*𝘛(n/2)+6*𝘛(n/5)+𝘛(n/10)+(n2)/ln(n)

Решение

1. Так как нам нужна оценка сверху то попробуем огрубить 𝘛(n):

   𝘛(n)=𝘛(n/4)+2*𝘛(n/16)+n*(log_2)(n)≤3*𝘛(n/4)+n*ln(n)

   Мастер теорему применить можно. Тогда a=3,b=4,c=1,ƒ(n)=ln(n)

   (log_b)(a)=(log_4)(3)<1, но c=1⇒(log_b)(a)<c⇒𝘛(n)=𝒪(nc*ƒ(n))=

   =𝒪(n*(log_)(n))

   Теперь воспользуемся теоремой Акра-Баззи:

   Найдем p:(1/4)p+2*(1/16)p=1. Произведем замену t= (1/4)p:

   2*t2+t-1=0. Корнями данного уравнения являются -1 и 1/2. Так как t=(1/4)p, то t>0 а значит имеет рассматривать только 1 из данных корней. Подставляем его: (1/4)p=1/2⇒p=1/2.

   После того как мы нашли p можно перейти к вычислению интеграла:

   (∫_1^n)((u*ln(u))/(u(3/2))*d(u))=√(,n)*(2*ln(n)-4)+4 - от ученика тут ждем вычислений

   Наконец подставим полученный результат в ассимптотическую формулу:

   𝘛(n)=ϴ(np*(1+√(,n)*ln(n)-4√(,n)))=ϴ(n*ln(n))

   Оценки по обоим теорема совпали, нам повезло так как вызово функции 𝘛(n) было не так много и даже после значительного огрубления оценка все еще оказалась верна, а так же исходная функция довольно предсказуемо влияет на ответ

2. Сначала вычислим точную оценку методом Аккра-Баззи:

   Найдем p=3*(1/2)p+6*(1/5)p+(1/10)p=1. Единственным корнем этого уравнения является p=2.

   Теперь можно вычислить интеграл:

   (∫_1^n)((u2)/ln(u)/(u3)*d(u))=(∫_1^n)(d(u)/(u*ln(u)))=(∣_1^n)(ln(ln(u)))=ln(ln(n))-ln(ln(1)) - от ученика здесь вычисления

   Теперь посчитаем финальный ответ:

   𝘛(n)=ϴ(np*(1+ln(ln(u))))=ϴ(n2*ln(ln(n)))

   Теперь попробуем применить мастер-теорему. Во первых мы столкнемся с той проблемой что функция (n2)/ln(n) не является монотонной на всем промежутке определения 𝘛(n), но этот промежуток можно ограничить в нашем случае. Далее нам придется сверху оценить размеры подзадач. Так как там стоит 1/5 и 1/10 то это довольно маленькие части по сравнению с 1/2 однако отбросить мы их не можем. Получим что:

   𝘛(n)=3*𝘛(n/2)+6*𝘛(n/5)+𝘛(n/10)+(n2)/ln(n)≤10*𝘛(n/2)+(n2)/ln(n)

   a=10, b=2⇒(log_b)(a)>3 но c=2, получается что разница довольно существенна и согласно обычной мастер теореме мы должны записать такую оценку сверху: 𝘛(n)=𝒪(n(log_b)(a)*ƒ(n))=𝒪((n3.322)/ln(n)) что кратно больше нашей точной оценки