Články

2.4: Riešenie opakovaných vzťahov


Príklad ( PageIndex {1} )

Nájdite vzťah opakovania a počiatočné podmienky pre (1, 5, 17, 53, 161, 485 ldots text {.} )

Riešenie

Nájdenie vzťahu opakovania by bolo jednoduchšie, keby sme mali nejaký kontext problému (napríklad Hanojská veža). Bohužiaľ, máme iba postupnosť. Pamätajte, že vzťah opakovania vám povie, ako sa dostať z predchádzajúcich výrazov do budúcich. Čo sa tu deje? Mohli by sme sa pozrieť na rozdiely medzi výrazmi: (4, 12, 36, 108, ldots text {.} ) Všimnite si, že sa zväčšujú s faktorom 3. Je pôvodná postupnosť tiež? (1 cdot 3 = 3 text {,} ) (5 cdot 3 = 15 text {,} ) (17 cdot 3 = 51 ) atď. Zdá sa, že vždy skončíme o 2 menej ako v nasledujúcom volebnom období. Aha!

Takže (a_n = 3a_ {n-1} + 2 ) je náš vzťah opakovania a počiatočná podmienka je (a_0 = 1 text {.} )


Vzťahy opakovania

A vzťah opakovania je rovnica, v ktorej je každý člen postupnosti definovaný ako funkcia predchádzajúcich členov.

Existujú rôzne spôsoby riešenia týchto vzťahov, ktoré preskúmame:

Riešenie rekurentných vzťahov opakovanou deriváciou / substitúciou

Predpokladom pre tento typ riešenia je neustále nahrádzať rekurentný vzťah na pravej strane (tj. Dosadiť hodnotu do pôvodnej rovnice a potom odvodiť predchádzajúcu verziu rovnice). Rôzne derivácie by mali viesť k zovšeobecnenej podobe rovnice, ktorú je možné vyriešiť pre časové obmedzenie algoritmu / rovnice: Napríklad:

Jedinou náhradou, ktorá je v tomto okamihu k dispozícii, je nahradiť n / 2 za n v pôvodnej rovnici:

Pridajte c na obe strany a odvodte pôvodnú rovnicu:

Teraz, keď bola odvodená ďalšia rovnica, existuje nová substitúcia, ktorú je možné urobiť v pôvodnom: n / 4 za n

Všeobecne platí, že základná rovnica je:

Predpoklad, že n = 2 k umožňuje:

Riešenie vzťahov opakovania pomocou teleskopu

Predpokladom pre tento typ riešenia je nahradiť hodnoty n, spočítať výsledky a vylúčiť podobné výrazy. Napríklad:


Majstrovská metóda

Na riešenie opakovaní formulára je použiteľná metóda Master
$ začať T (n) = aT vľavo ( frac vpravo) + f (n) koniec$
kde $ a ge 0 $ a $ b ge 1 $ sú konštanty a $ f (n) $ je asymptoticky pozitívna funkcia. V závislosti od hodnoty $ a, b $ a funkcie $ f (n) $ má hlavná metóda tri prípady.

  1. Ak $ f (n) = O (n ^ < log_b a- epsilon>) $ pre nejakú konštantu $ epsilon> 0 $, potom $ T (n) = Theta (n ^ < log_b a>) $ .
  2. Ak $ f (n) = Theta (n ^ < log_b a>) $, potom $ T (n) = Theta (n ^ < log_b a> log n) $.
  3. Ak $ f (n) = Omega (n ^ < log_b a + epsilon>) $ pre nejakú konštantu $ epsilon> 0 $, a ak $ af (n / b) le cf (n) $ pre niektoré konštanta $ c 0 $ je konštanta pre $ i le i le k $
  4. $ b_i in (0, 1) $ je konštanta pre $ 1 le i le k $
  5. $ k ge 1 $ je konštanta a,
  6. $ f (n) $ je nezáporná funkcia

Riešením rekurencie uvedeným v bode 2 je,
$ T (n) = Theta vľavo (n ^ p vľavo (1 + int_ <1> ^ frac<>

> du right) right) $
Za predpokladu,
$ sum_^a_ib_i ^ p = 1 text $

Príklad 1: Zvážte opakovanie,
$ T (n) = 2T (n / 4) + 3T (n / 6) + Theta (n log n) $

Pre toto opakovanie $ a_1 = 2, b_1 = 1/4, a_2 = 3, b_2 = 1/6, f (n) = n log n $. Hodnota $ p $ sa dá vypočítať ako,
$ a_1b_1 ^ p + a_2b_2 ^ p = 2 krát (1/4) ^ p + 3 krát (1/6) ^ p = 1 $
$ p = 1 $ spĺňa vyššie uvedenú rovnicu. Riešením je
$ začať T (n) & = Theta doľava (n ^ p doľava (1 + int_ <1> ^ frac<>

> du right) right)
& = Theta doľava (n doľava (1 + int_ <1> ^ frac du right) right)
& = Theta vľavo (n vľavo (1 + frac < log ^ 2n> <2> vpravo) vpravo)
& = Theta (n log ^ 2n)
koniec$


Metóda spätnej substitúcie

Pri doprednej substitučnej metóde vložíme $ n = 0, 1, 2, ... $ do vzťahu opakovania, kým neuvidíme vzor. Pri spätnej substitúcii urobíme opak, t. J. Vložíme $ n = n, n - 1, n - 2,… $ alebo $ n = n, n / 2, n / 4,… $, kým neuvidíme vzor. Keď uvidíme vzor, ​​urobíme dohady pre čas behu a overíme si dohady. Použime túto metódu na niekoľkých príkladoch.

Zvážte príklad vzťahu rekurencie uvedený nižšie
$ T (n) = začať 1 & text n = 1 2T vľavo ( frac <2> vpravo) + n & text koniec$

Vzhľadom na $ T (n) $ môžeme z vyššie uvedeného vzťahu opakovania vypočítať hodnotu $ T (n / 2) $ ako
$ T (n / 2) = 2T vľavo ( frac <4> vpravo) + frac<2>$
Teraz vrátime späť hodnotu $ T (n / 2) $ v $ T (n) $
$ T (n) = 2 ^ 2T vľavo ( frac<2 ^ 2> vpravo) + 2n $
Postupujeme obdobne
$ začaťT (n) & = 2 ^ 3T vľavo ( frac <2 ^ 3> vpravo) + 3n
& = 2 ^ 4T vľavo ( frac <2 ^ 4> vpravo) + 4n
& = 2 ^ kT vľavo ( frac <2 ^ k> vpravo) + kn
koniec$
Teraz by sme mali použiť hraničnú (základnú) podmienku, tj. $ T (1) = 1 $. Aby bolo možné použiť okrajovú podmienku, musí byť entita vo vnútri $ T () $ 1, t.j.
$ frac <2 ^ k> = 1 $
Vezmeme $ log_2 $ na oboch stranách,
$ n = log_2 n $
Rovnica (6) sa stáva
$ začať
T (n) & = 2 ^ < log_2 n> T vľavo ( frac<2 ^ < log_2 n >> vpravo) + log_2 n.n
& = nT (1) + n log_2 n
& = n log_2 n + n
koniec$
Správnosť vyššie uvedeného prevádzkového času je možné dokázať pomocou indukcie. Vložte $ n = 2, 4, 8, 16, ... $ a môžete ľahko overiť, či je odhadovaný čas skutočne správny.

V praktických prípadoch zriedka používame substitučnú metódu dopredu a dozadu. Existujú oveľa sofistikovanejšie a rýchlejšie metódy. Tieto metódy však možno použiť ako poslednú možnosť, keď iné metódy nie sú schopné vyriešiť niektoré druhy recidív.


2.4: Riešenie opakovaných vzťahov

V predchádzajúcom príspevku sme sa zaoberali analýzou slučiek. Mnoho algoritmov má rekurzívnu povahu. Keď ich analyzujeme, dostaneme vzťah opakovania pre časovú zložitosť. Dostaneme čas behu na vstupe veľkosti n ako funkciu n a čas behu na vstupoch menších veľkostí. Napríklad v Merge Sort, aby sme zoradili dané pole, rozdelíme ho na dve polovice a rekurzívne opakujeme postup pre dve polovice. Nakoniec zlúčime výsledky. Časovú zložitosť zlúčenia je možné zapísať ako T (n) = 2T (n / 2) + cn. Existuje mnoho ďalších algoritmov, ako sú Binárne vyhľadávanie, Hanojská veža atď.

Existujú hlavne tri spôsoby riešenia recidív.

1) Substitučná metóda: Urobíme odhad riešenia a potom pomocou matematickej indukcie potvrdíme, že odhad je správny alebo nesprávny.

2) Metóda stromu recidívy: V tejto metóde nakreslíme strom opakovania a vypočítame čas potrebný na každej úrovni stromu. Na záver zhrnieme prácu vykonanú na všetkých úrovniach. Ak chcete nakresliť strom opakovania, vychádzame z daného opakovania a pokračujeme v kreslení, kým nenájdeme vzor medzi úrovňami. Vzor je zvyčajne aritmetický alebo geometrický rad.

3) Hlavná metóda:
Hlavná metóda je priamym spôsobom získania riešenia. Hlavná metóda funguje iba pre nasledujúci typ opakovaní alebo pre opakovania, ktoré je možné transformovať na nasledujúci typ.

Existujú nasledujúce tri prípady:
1. Ak f (n) = O (n c), kde c & lt Logba potom T (n) = Θ (n Log b a)

2. Ak f (n) = Θ (n c) kde c = Logba potom T (n) = Θ (n c Log n)

3.Ak f (n) = Ω (n c), kde c> Logba potom T (n) = Θ (f (n))

Ako to funguje?
Hlavná metóda je odvodená hlavne z metódy stromu rekurencie. Ak nakreslíme strom rekurencie T (n) = aT (n / b) + f (n), môžeme vidieť, že práca vykonaná v koreňovom adresári je f (n) a práca vykonaná na všetkých listoch je Θ (nc), kde c je Logba. A výška stromu opakovania je Logbn

Pri metóde stromu rekurencie počítame celkovú vykonanú prácu. Ak je práca vykonaná na listoch polynomiálne viac, potom sú listy dominantnou časťou a naším výsledkom sa stane práca vykonaná na listoch (prípad 1). Ak sú práce vykonané na listoch a koreňoch asymptoticky rovnaké, potom sa naším výsledkom stane výška vynásobená prácou na akejkoľvek úrovni (prípad 2). Ak je práca vykonaná v koreňovom adresári asymptoticky viac, potom sa naším výsledkom stane práca v koreňovom adresári (prípad 3).

Príklady niektorých štandardných algoritmov, ktorých časovú zložitosť je možné vyhodnotiť pomocou hlavnej metódy
Zlúčiť zoradenie: T (n) = 2T (n / 2) + Θ (n). Padá v prípade 2, pretože c je 1 a Logba] je tiež 1. Takže riešenie je Θ (n Logn)

Binárne vyhľadávanie: T (n) = T (n / 2) + Θ (1). To tiež spadá do prípadu 2, pretože c je 0 a Logba je tiež 0. Takže riešenie je Θ (Logn)

Poznámky:
1) Nie je potrebné, aby sa opakovanie tvaru T (n) = aT (n / b) + f (n) dalo vyriešiť pomocou hlavnej vety. Uvedené tri prípady majú medzi sebou určité medzery. Napríklad opakovanie T (n) = 2T (n / 2) + n / Logn nemožno vyriešiť pomocou hlavnej metódy.

2) Prípad 2 je možné predĺžiť pre f (n) = Θ (n c Log k n)
Ak f (n) = Θ (n c Log k n) pre nejakú konštantu k> = 0 a c = Logba, potom T (n) = Θ (n c Log k + 1 n)

Ak nájdete niečo nesprávne alebo chcete zdieľať viac informácií o vyššie diskutovanej téme, napíšte komentáre

Pozor čitateľ! Don & rsquot prestať učiť sa teraz. Chyťte všetky dôležité koncepty DSA pomocou Samozrejmý kurz DSA za študentskú cenu a pripravte sa na priemysel. Ak chcete dokončiť svoju prípravu od výučby jazyka po program DS Algo a mnoho ďalších, prečítajte si Kompletný kurz prípravy rozhovoru.


2.4: Riešenie opakovaných vzťahov

Metóda rekurzívneho stromu je spôsob riešenia rekurentných vzťahov. V tejto metóde sa relacia rekurencie prevádza na rekurzívne stromy. Každý uzol predstavuje náklady vzniknuté na rôznych úrovniach rekurzie. Na zistenie celkových nákladov sa sčítajú náklady všetkých úrovní.

  1. Nakreslite rekurzívny strom pre daný vzťah opakovania
  2. Vypočítajte náklady na každej úrovni a spočítajte celkový počet úrovní v rekurzívnom strome.
  3. Spočítajte celkový počet uzlov na poslednej úrovni a vypočítajte náklady na poslednú úroveň
  4. Zhrňte náklady na všetky úrovne v rekurzívnom strome

Pozrime sa, ako vyriešiť tieto vzťahy opakovania pomocou niekoľkých príkladov:

Otázka 1: T (n) = 2T (n / 2) + c

  • Krok 2: Vypočítajte vykonanú prácu alebo náklady na každej úrovni a spočítajte celkový počet úrovní v rekurzívnom strome

Rekurzívny strom s každou úrovňou nákladov

Spočítajte celkový počet úrovní # 8211

Vyberte najdlhšiu cestu od koreňového uzla k listovému uzlu

Veľkosť problému na poslednej úrovni = n / 2 k

Na poslednej úrovni sa veľkosť problému zmení na 1

Celkový počet úrovní v rekurzívnom strome = k +1 = log2(n) + 1

  • Krok 3: Spočítajte celkový počet uzlov na poslednej úrovni a vypočítajte náklady na poslednú úroveň

T (n) = c + 2c + 4c + & # 8212- + (počet úrovní-1) -krát + náklady na poslednú úroveň

= c + 2c + 4c + & # 8212- + denník2(n) -krát + Θ (n)

= c (1 + 2 + 4 + & # 8212- + log2(n) -krát) + Θ (n)

1 + 2 + 4 + & # 8212 & # 8211 + denník2(n) krát & # 8211> 2 0 + 2 1 + 2 2 + & # 8212 & # 8211 + log2 (n) krát & # 8211> Geometrická progresia (GP)

= c (n) + Θ (n)


Teda T (n) = Θ (n)

Otázka 2: T (n) = T (n / 10) + T (9n / 10) + n

  • Krok 2: Vypočítajte vykonanú prácu alebo náklady na každej úrovni a spočítajte celkový počet úrovní v rekurzívnom strome

Rekurzívny strom s každou úrovňou nákladov

Spočítajte celkový počet úrovní # 8211

Vyberte najdlhšiu cestu od koreňového uzla k listovému uzlu

(9/10) 0 n & # 8211> (9/10) 1 n & # 8211> (9/10) 2 n & # 8211> & # 8230 & # 8230 & # 8230 & # 8211> (9/10) k n

Veľkosť problému na poslednej úrovni = (9/10) k n

Na poslednej úrovni sa veľkosť problému zmení na 1

(9/10) k n = 1

(9/10) k = 1 / n

k = log10/9(n)

  • Krok 3: Spočítajte celkový počet uzlov na poslednej úrovni a vypočítajte náklady na poslednú úroveň

Pozor čitateľ! Don & rsquot prestať učiť sa teraz. Precvičte si skúšku GATE dobre pred samotnou skúškou pomocou predmetových a celkových kvízov dostupných v jazyku Kurz testovacej série GATE.


3.2. Keď T (n) = aT (n-1) + f (n)

To je trochu zložitejšie, pretože ako argumenty pre pokles f sa vynásobia ďalšími a ďalšími. Po určitej spätnej substitúcii nie je ťažké rozpoznať vzor

Príklad: T (n) = 2T (n-1) + n. Potom zo vzorca

Ukázalo sa, že je to dosť bolestivá suma, ktorú je potrebné presne vyriešiť. Môžeme však rozumne hádať, že je niekde medzi 2 n a 2 n n, a pokúsiť sa odhadnúť, ale overiť, aby sa rozsah ďalej zmenšil.


Riešenie nelineárnych vzťahov