Metoda Akra – Bazzi - Akra–Bazzi method

Tento článek obsahuje seznam obecných Reference, ale zůstává z velké části neověřený, protože postrádá dostatečné odpovídající vložené citace. Prosím pomozte zlepšit tento článek představuji přesnější citace. (únor 2013) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

v počítačová věda, Metoda Akra – Bazzinebo Věta Akra – Bazzi, se používá k analýze asymptotického chování matematiky opakování které se objevují v analýze rozděl a panuj algoritmy kde dílčí problémy mají podstatně odlišné velikosti. Jedná se o zobecnění hlavní věta o opakování rozděli a panuj, který předpokládá, že dílčí problémy mají stejnou velikost. Je pojmenována podle matematiků Mohamad Akra a Louay Bazzi.^[1]

Formulace

Metoda Akra – Bazzi platí pro opakovací vzorce formuláře^[1]

${ displaystyle T (x) = g (x) + součet _ {i = 1} ^ {k} a_ {i} T (b_ {i} x + h_ {i} (x)) qquad { text {for}} x geq x_ {0}.}$

Podmínky pro použití jsou:

• jsou poskytnuty dostatečné základní případy
• ${ displaystyle a_ {i}}$ a ${ displaystyle b_ {i}}$ jsou konstanty pro všechny ${ displaystyle i}$
• ${ displaystyle a_ {i}> 0}$ pro všechny ${ displaystyle i}$
• ${ displaystyle 0$ pro všechny ${ displaystyle i}$
• ${ displaystyle left | g (x) right | v O (x ^ {c})}$, kde C je konstanta a Ó notátoři Velká O notace
• ${ displaystyle left | h_ {i} (x) right | in O left ({ frac {x} {( log x) ^ {2}}} right)}$ pro všechny ${ displaystyle i}$
• ${ displaystyle x_ {0}}$ je konstanta

Asymptotické chování ${ displaystyle T (x)}$ se zjistí určením hodnoty ${ displaystyle p}$ pro který ${ displaystyle sum _ {i = 1} ^ {k} a_ {i} b_ {i} ^ {p} = 1}$ a zapojením této hodnoty do rovnice^[2]

${ displaystyle T (x) v Theta vlevo (x ^ {p} vlevo (1+ int _ {1} ^ {x} { frac {g (u)} {u ^ {p + 1 }}} du right) right)}$

(vidět Θ ). Intuitivně, ${ displaystyle h_ {i} (x)}$ představuje malou poruchu v indexu ${ displaystyle T}$. Tím, že si to všimli ${ displaystyle lfloor b_ {i} x rfloor = b_ {i} x + ( lfloor b_ {i} x rfloor -b_ {i} x)}$ a že absolutní hodnota ${ displaystyle lfloor b_ {i} x rfloor -b_ {i} x}$ je vždy mezi 0 a 1, ${ displaystyle h_ {i} (x)}$ lze použít k ignorování funkce podlahy v indexu. Podobně lze také ignorovat stropní funkce. Například, ${ displaystyle T (n) = n + T vlevo ({ frac {1} {2}} n doprava)}$ a ${ displaystyle T (n) = n + T vlevo ( vlevo lfloor { frac {1} {2}} n vpravo rfloor vpravo)}$ bude mít podle věty Akra – Bazzi stejné asymptotické chování.

Příklad

Předpokládat ${ displaystyle T (n)}$ je definována jako 1 pro celá čísla ${ displaystyle 0 leq n leq 3}$ a ${ displaystyle n ^ {2} + { frac {7} {4}} T left ( left lfloor { frac {1} {2}} n right rfloor right) + T left ( left lceil { frac {3} {4}} n right rceil right)}$ pro celá čísla ${ displaystyle n> 3}$. Při použití metody Akra – Bazzi je prvním krokem nalezení hodnoty ${ displaystyle p}$ pro který ${ displaystyle { frac {7} {4}} vlevo ({ frac {1} {2}} vpravo) ^ {p} + vlevo ({ frac {3} {4}} vpravo) ^ {p} = 1}$. V tomto příkladu ${ displaystyle p = 2}$. Potom pomocí vzorce lze asymptotické chování určit takto:^[3]

${ displaystyle { begin {aligned} T (x) & in Theta left (x ^ {p} left (1+ int _ {1} ^ {x} { frac {g (u)}) {u ^ {p + 1}}} , du right) right) & = Theta left (x ^ {2} left (1+ int _ {1} ^ {x} { frac {u ^ {2}} {u ^ {3}}} , du right) right) & = Theta (x ^ {2} (1+ ln x)) & = Theta (x ^ {2} log x). End {zarovnáno}}}$

Význam

Metoda Akra – Bazzi je pro stanovení asymptotického chování užitečnější než většina ostatních technik, protože pokrývá tak širokou škálu případů. Jeho primární aplikací je aproximace runtime mnoha algoritmů rozděl a panuj. Například v Sloučit třídění, počet srovnání požadovaných v nejhorším případě, který je zhruba úměrný jeho době běhu, je uveden rekurzivně jako ${ displaystyle T (1) = 0}$ a

${ displaystyle T (n) = T left ( left lfloor { frac {1} {2}} n right rfloor right) + T left ( left lceil { frac {1} { 2}} n pravý rceil pravý) + n-1}$

pro celá čísla ${ displaystyle n> 0}$, a lze jej tedy vypočítat pomocí metody Akra – Bazzi ${ displaystyle Theta (n log n)}$.

Viz také

• Masterova věta (analýza algoritmů)
• Asymptotická složitost

Reference

externí odkazy

• O Método de Akra-Bazzi na Resolução de Equações de Recorrência (v portugalštině)