X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=8-fft%2F8-fft.tex;h=9f182dccafc5abb446fc8a51fe03934dd49e4d40;hb=c3db7103f942ee420b7d525802bbc6b9b2a98b90;hp=2b9da46da0a8b06f3b9a3dd7b19201f3a0969527;hpb=303a617310903c1543eb1415c96b79d1d96e4157;p=ads2.git diff --git a/8-fft/8-fft.tex b/8-fft/8-fft.tex index 2b9da46..9f182dc 100644 --- a/8-fft/8-fft.tex +++ b/8-fft/8-fft.tex @@ -1,165 +1,161 @@ \input lecnotes.tex \prednaska{8}{Fourierova transformace}{(K.Jakubec, M.Polák a G.Ocsovszky)} -Násobení polynomù mù¾e mnohým pøipadat jako pomìrnì (algoritmicky) snadný problém. Asi ka¾dého hned napadne "hloupý" algoritmus - jednodu¹e vezmu koeficienty prvního polynomu a ka¾dým z nich pøenásobím v¹echny koeficienty toho druhého. Pokud øád prvního polynomu je $n$ a druhého $m$, tak èasová slo¾itost nám vyjde nìco jako $O(mn)$. To není a¾ tak ¹patné, v nejhor¹ím se dostaneme na $O(n^{2})$ (pokud $m = n$). Na první pohled se mù¾e zdát, ¾e rychleji to prostì nejde (pøeci musím v¾dy vynásobit "ka¾dej s ka¾dým"). Ve skuteènosti to ale rychleji fungovat mù¾e...ale k tomu je potøeba znát trochu tajemný algoritmus FFT neboli {\I Fast Fourier Transform}. +Násobení polynomù mù¾e mnohým pøipadat jako pomìrnì (algoritmicky) snadný problém. Asi ka¾dého hned napadne \uv{hloupý} algoritmus -- jednodu¹e vezmeme koeficienty prvního polynomu a ka¾dým z nich pøenásobím v¹echny koeficienty toho druhého. Pokud øád prvního polynomu je $n$ a druhého $m$, tak èasová slo¾itost nám vyjde nìco jako $\O(mn)$. To není a¾ tak ¹patné, v nejhor¹ím pøípadì se dostaneme na $\O(n^{2})$ (pokud $m = n$). Na první pohled se mù¾e zdát, ¾e rychleji to prostì nejde (pøeci musíme v¾dy vynásobit \uv{ka¾dej s ka¾dým}). Ve skuteènosti to ale rychleji fungovat mù¾e, ale k~tomu je potøeba znát trochu tajemný algoritmus FFT neboli {\I Fast Fourier Transform}. -\s{ Trochu algebry na zaèátek: } - -Libovolný polynom P øádu n mù¾eme mít reprezentován 2 rùznými zpùsoby: +\ss{Trochu algebry na zaèátek:} +\>Libovolný polynom $P$ øádu $n$ mù¾eme být reprezentován dvìma rùznými zpùsoby: \itemize\ibull -\: jeho koeficienty, èili èísly $a_{0}, a_{1}, \ldots ,a_{n}$ -\: jeho hodnotami v n + 1 rùzných bodech $x_{0}, x_{1}, \ldots , x_{n+1}$ èili èísly $P(x_{0} ), P(x_{1} ), \ldots ,P( x_{n+1} )$ -\: +\:svými koeficienty, èili èísly $a_{0}, a_{1}, \ldots ,a_{n}$, nebo +\:svými hodnotami v $n + 1$ rùzných bodech $x_{0}, x_{1}, \ldots , x_{n}$, èili èísly $P(x_{0}),$ $P(x_{1}),$ $\ldots , P(x_{n})$. \endlist -Pov¹imnìme si jedné skuteènosti - máme-li 2 polynomy $A$ a $B$ øádu $n$ a $x_{0}\ldots, x_{k}$ body, pak platí $C(x_{k}) = A(x_{k}) * B(x_{k}), k = 0,1,2 \ldots n+1.$ Toto èiní tento druhý zpùsob reprezentace polynomu velice atraktivním pro násobení. Problémem je, ¾e typicky máme polynom zadaný koeficienty a ne hodnotami v bodech. Tím pádem potøebujeme nìjaký hodnì rychlý algorimtus (= rychlej¹í ne¾ kvadratický, jinak bychom si nepomohli oproti hloupému algoritmu) na pøevod polynomu z jedné reprezentace do druhé a zase zpìt. +\>Pov¹imnìme si jedné skuteènosti -- máme-li dva polynomy $A$ a $B$ øádu $n$ a body $x_{0}, \ldots, x_{k}$, pak platí $C(x_{k}) = A(x_{k}) \cdot B(x_{k}), k = 0,1,2, \ldots, n+1.$ Toto èiní tento druhý zpùsob reprezentace polynomu velice atraktivním pro násobení. Problémem je, ¾e typicky máme polynom zadaný koeficienty a ne hodnotami v bodech. Tím pádem potøebujeme nìjaký hodnì rychlý algorimtus (tj. rychlej¹í ne¾ kvadratický, jinak bychom si nepomohli oproti hloupému algoritmu) na pøevod polynomu z~jedné reprezentace do druhé a zase zpìt. -Dále bychom si mìli uvìdomit, ¾e stupeò na¹eho výsledného polynomu C bude $\leq 2n+1$ (kde $n$ je stupnìm výchozích polynomù). To snad netøeba nijak vysvìtlovat, ka¾dý si to snadno ovìøí, jen dodáme, ¾e pokud chceme polynom C reprezentovat pomocí jeho hodnot v bodech, musíme vzít $2n + 2$ bodù. Tímto konèí malá algebraická vsuvka. +Dále bychom si mìli uvìdomit, ¾e stupeò na¹eho výsledného polynomu $C$ bude $\leq 2n+1$ (kde $n$ je stupnìm výchozích polynomù). To snad netøeba nijak vysvìtlovat, ka¾dý si to snadno ovìøí, jen dodáme, ¾e pokud chceme polynom $C$ reprezentovat pomocí jeho hodnot v bodech, musíme vzít $2n + 2$ bodù. Tímto konèí malá algebraická vsuvka. -\s{ Idea, jak by mìl algorimus pracovat: } -\itemize\ibull -\: vybereme 2n + 2 bodù $x_{0}, x_{1}, \ldots , x_{2n+2}$ -\: v tìchto bodech vyhodnotíme polynomy $A$ a $B$ -\: nyní ji¾ v lineárním èase získám polynom C (viz vý±e) -\: invernznì pøevedu hodnoty polynomu C v 2n+2 bodech na jeho koeficienty -\endlist +\s{Idea, jak by mìl algoritmus pracovat:} +\algo +\:Vybereme $2n + 2$ bodù $x_{0}, x_{1}, \ldots , x_{2n+1}$. +\:V~tìchto bodech vyhodnotíme polynomy $A$ a $B$. +\:Nyní ji¾ v lineárním èase získáme polynom $C$ (viz vý¹e). +\:Inverznì pøevedeme hodnoty polynomu $C$ v $2n+2$ bodech na jeho koeficienty. +\endalgo -Je asi vidìt, µe klíèové jsou kroky 2 a 4. Vybrání bodù jistì stihneneme pohodlnì v lineárním èas a vynásobení samotných hodnot té¾ (máme 2n+2 bodù, a $C(x_{k}) = A(x_{k}) * B(x_{k}), k = 0,1,2 \ldots 2n+2$, tak¾e na to nepotøebujeme více ne¾ $2n+2$ násobení). +\>Je asi vidìt, ¾e klíèové jsou kroky 2 a 4. Vybrání bodù jistì stihneme pohodlnì v~lineárním èase a vynásobení samotných hodnot té¾ (máme $2n+2$ bodù a $C(x_{k}) = A(x_{k}) \cdot B(x_{k}), k = 0,1,2, \ldots , 2n+1$, tak¾e na to nepotøebujeme více ne¾ $2n+2$ násobení). -Celý trik spoèívá v chytrém vybrání onìch bodù, ve kterých budeme polynomy vyhodnocovat. Je na to potøeba vìdìt pár zajímavostí o komplexních èíslech, na stránce Matrina Mar¹e jsou k dispozici slajdy, zde to bude zapsáno o trochu struènìji. +Celý trik spoèívá v~chytrém vybrání onìch bodù, ve kterých budeme polynomy vyhodnocovat. Je na to potøeba vìdìt pár zajímavostí o~komplexních èíslech, na stránce Matrina Mar¹e jsou k dispozici slajdy, zde to bude zapsáno o~trochu struènìji. -\s{ Vyhodnocení polynomu metodou rozdìl a panuj (algoritmus FFT): } -Mìjme polynom P øádu $n$ a chceme jej vyhonotit v $n$ bodech. Vybereme si body tak, aby byly spárované, èili $\pm x_{0}, \pm x_{1} \ldots \pm x_{n/2-1} $. To nám výpoèet urychlí, proto¾e pak se druhé mocniny $x_{i}$ shodují s~druhými mocninami $-x_{i}$. +\ss{Vyhodnocení polynomu metodou rozdìl a panuj (algoritmus FFT):} +Mìjme polynom $P$ øádu $n$ a chceme jej vyhodnotit v $n$ bodech. Vybereme si body tak, aby byly spárované, èili $\pm x_{0}, \pm x_{1}, \ldots , \pm x_{n/2-1} $. To nám výpoèet urychlí, proto¾e pak se druhé mocniny $x_{i}$ shodují s~druhými mocninami $-x_{i}$. -Polynom P rozlo¾íme na dvì èásti, první obsahuje èleny se sudými koeficienty, druhá s lichými: +Polynom $P$ rozlo¾íme na dvì èásti, první obsahuje èleny se sudými exponenty, druhá s~lichými: $P(x) = p_{0}x^{0} + p_{2}x^{2} + \ldots + p_{n-2}x^{n-2} + p_{1}x^{1} + p_{3}x^{3} + \ldots + p_{n-1}x^{n-1}$ -$S(x^{2}) = p_{0}x^{0} + p_{2}x^{2} + ... + p_{n - 2}x^{n - 2}$ -$L(x^{2}) = p_{1}x^{1} + p_{3}x^{3} + ... + p_{n - 1}x^{n - 1}$ +$S(x^{2}) = p_{0}x^{0} + p_{2}x^{2} + \ldots + p_{n - 2}x^{n - 2}$, +$L(x^{2}) = p_{1}x^{1} + p_{3}x^{3} + \ldots + p_{n - 1}x^{n - 1}$ -Tak¾e obecnì $P(x) = S(x^{2}) + xL(x^{2})$ a $P(-x) = S(x^{2}) - xL(x^{2})$ -Jinak øeèeno, vyhodnocování P(x) v $n$ bodech se nám smrskne na vyhodnocení $S(x)$ a $L(x)$ (oba mají polovièní stupeò ne¾ P(x)) v $n/2$ bodech (proto¾e $(x_{i})^{2} = (-x_{i})^{2}$). +\>Tak¾e obecnì $P(x) = S(x^{2}) + xL(x^{2})$ a $P(-x) = S(x^{2}) - xL(x^{2})$. +Jinak øeèeno, vyhodnocování $P(x)$ v $n$ bodech se nám smrskne na vyhodnocení $S(x)$ a $L(x)$ (oba mají polovièní stupeò ne¾ $P(x)$) v $n/2$ bodech (proto¾e $(x_{i})^{2} = (-x_{i})^{2}$). -Pøíklad: -$3 + 4x + 6x^{2} + 2x^{3} + x^{4} + 10x^{5} = (3 + 6x^{2} + x^{4}) + x(4 + 2x^{2} + 10x^{4}):$ +\s{Pøíklad:} +$3 + 4x + 6x^{2} + 2x^{3} + x^{4} + 10x^{5} = (3 + 6x^{2} + x^{4}) + x(4 + 2x^{2} + 10x^{4})$. -Teï nám ov¹em vyvstane problém s oním párováním - druhá mocina pøece nemù¾e být záporná a tím pádem v u¾ v druhém levlu rekurze body spárované nebudou. Z tohoto dùvodu musíme pou¾ít komplexní èísla - tam druhé mocniny záporné býti mohou. Jako $x_{0} \ldots x_{n-1} $ si zvolíme n-tou komplexní odmocninu z 1. Máme n n-tých odmocnin z 1, rovnomìrnì rozesetých po jednotkové kru¾nici, búno $n=2^{k}, k \in N$ (jinak viz slajdy Martina Mare¹e). Jednotlivé odmociny vypadají takto: $1, \omega, \omega^{2} \ldots \omega^{n - 1} $, kde $\omega = e^{2 \pi i/ n}$. 2 poznámky: +Teï nám ov¹em vyvstane problém s oním párováním -- druhá mocina pøece nemù¾e být záporná a tím pádem u¾ v~druhé úrovni rekurze body spárované nebudou. Z~tohoto dùvodu musíme pou¾ít komplexní èísla -- tam druhé mocniny záporné býti mohou. Jako $x_{0}, \ldots , x_{n-1} $ si zvolíme $n$-tou komplexní odmocninu z~jedné. Máme $n$ $n$-tých odmocnin z jednièky, rovnomìrnì rozesetých po jednotkové kru¾nici, BÚNO $n=2^{k}, k \in N$ (jinak viz slajdy Martina Mare¹e). Jednotlivé odmociny vypadají takto: $1, \omega, \omega^{2}, \ldots , \omega^{n - 1} $, kde $\omega = e^{2 \pi i/ n}$. + +\s{Dvì poznámky:} \itemize\ibull -\: n-té odmocniny z 1 jsou spárované, èili $\omega^{j} = -\omega^{n/2 + j} $ -\: umocníme-li v¹echny na druhou, vznikne nám n/2 n-pùltých odmocnin z 1, které jsou i nadále spárované +\:$n$-té odmocniny z~jednièky jsou spárované, èili $\omega^{j} = -\omega^{n/2 + j}$, +\:umocníme-li v¹echny na druhou, vznikne nám $n/2$ $n/2$-tých odmocnin z~jedné, které jsou i nadále spárované. \endlist -\s{Tak a teï koneènì ten slavný algoritmus: } -FFT(P, $ \omega$) -Vstup: $p_{0} \ldots p_{n-1}$ to jest vektor koeficientù polynomu P a $\omega$ co¾ je n-tá odmocina 1 -Výstup: Hodnoty polynomu v bodech $1, \omega, \omega^{2} \ldots \omega^{n - 1}$ èili èísla $P(1), P(\omega), P(\omega^{2}), \ldots P(\omega^{n - 1})$ +\ss{Tak a teï koneènì ten slavný algoritmus:} +\>FFT($P$, $ \omega$) + +\>{\sl Vstup:} $p_{0}, \ldots , p_{n-1}$, koeficienty polynomu $P$, a $\omega$, $n-$tá odmocina z~jedné. + +\>{\sl Výstup:} Hodnoty polynomu v~bodech $1, \omega, \omega^{2}, \ldots , \omega^{n - 1}$, èili èísla $P(1), P(\omega), P(\omega^{2}),$ $\ldots , P(\omega^{n - 1})$. + \algo -\: pokud n = 1, vra» $P_{0}$ a konec -\: jinak rozdìl P na sudé a liché koeficienty a zarekurzi se FFT(S, $\omega^{2}$) a FFT(L, $\omega^{2}$) -\: pro $j = 0 \ldots n - 1$ spoèítej: $P(\omega^{j}) = S(\omega^{2j}) + \omega^{j} * L(\omega^{2j})$ +\:Pokud $n = 1$, vra» $P_{0}$ a konec. +\:Jinak rozdìl $P$ na sudé a liché koeficienty a zarekurzi se do FFT($S$, $\omega^{2}$) a FFT($L$, $\omega^{2}$). +\:Pro $j = 0, \ldots , n - 1$ spoèítej: $P(\omega^{j}) = S(\omega^{2j}) + \omega^{j} \cdot L(\omega^{2j})$. \endalgo -\s{ Èasová slo¾itost:} - $T(n)=2T({n \over 2} ) + O(n) \Rightarrow$ slouitost $O(n)$ ... stejnì jako MergeSort. +\s{Èasová slo¾itost:} +\>$T(n)=2T({n \over 2} ) + \O(n) \Rightarrow$ slo¾itost $\O(n \log n)$, stejnì jako MergeSort. -Máme tedy algoritmus, který "pøevede" koeficienty polynomu na hodnoty tohoto polynomu v námi zadaných bodech. Ale potøebujeme také algoritmus, který doká¾e reprezentaci polynomu pomocí hodnot pøevést zpìt na koeficienty polynomu. Tedy nìjaký inverzní algoitmus. -Definuje me si DFT algoritmus, která vyu¾ívá maticovou reprezentaci a s jeho¾ pomocí získáme hledaný algoritmus. +Máme tedy algoritmus, který \uv{pøevede} koeficienty polynomu na hodnoty tohoto polynomu v~námi zadaných bodech. Ale potøebujeme také algoritmus, který doká¾e reprezentaci polynomu pomocí hodnot pøevést zpìt na koeficienty polynomu. Tedy nìjaký inverzní algoitmus. +Definuje me si algoritmus DFT, která vyu¾ívá maticovou reprezentaci a s~jeho¾ pomocí získáme hledaný algoritmus. \s{Definice:} - - {\sc Diskretní Fourierova transformace} $(DFT)$ -je funkce $f: { C ^n} -> { C ^n}$ , ze $y=f(x) \equiv \forall j \ y_{j} = \sum \limits ^{n-1}_{k=0} x_{k} . \omega ^{k} $ +\>{\I Diskretní Fourierova transformace} $(DFT)$ +je funkce $f: { {\bb C} ^n} \rightarrow { {\bb C} ^n}$, kde $y=f(x) \equiv \forall j \ y_{j} = \sum \limits ^{n-1}_{k=0} x_{k} . \omega ^{jk}$. \s{Poznámka:} +Vezmeme polynom, který má $x_{kj}$ jako koeficienty a vyhodnotíme ho v~bodì $\omega ^{j} [y_{j} = x(\omega^{j})] \Rightarrow {f}$ je linearní $\Rightarrow$ mù¾eme napsat $f(x) = \Omega_{x} ,\ \Omega _{jk} =\omega ^{jk}$, kde $\Omega$ je matice. -Vezmeme polynom, který má $x_{kj}$ jako koeficienty a vyhodnotíme ho v bodì $\omega ^{j} [y_{j} = x(\omega^{j})] => {f}$ je linearní $=>$ mù¾eme napsat $f(x) = \Omega_{x} ,\ \Omega _{jk} =\omega ^{jk}$, kde $\Omega$ je matice +\s{Jak najít inverzní matici?} Víme, ¾e $\Omega =\Omega ^{T}$ proto¾e $\omega ^{jk} = \omega ^{kj}$. -\s{Jak najít inverzní matici?} Víme ¾e $\Omega =\Omega ^{T}$ protoue $\omega ^{jk} = \omega ^{kj}$ . +\ss{Jak vypadají øádky této matice?} +Vyu¾ijeme následující lemma, které si ale napøed doká¾eme :) -\s{Jak vypadají øádky této matice?} Vyu¾ijeme následující lemma, které si ale napøed doká¾eme :) +\ss{Lemma:} -\s{Lemma:} +\proof Souèin +$$\Omega _{j} \Omega _{k} = \sum \limits ^{n-1}_{l=0} \Omega _{jl} \overline{\Omega _{kl}} = \sum \limits _{l} \omega ^{jl} \overline{\omega ^{kl}} = \sum \limits _{l} \omega ^{jl} \omega ^{-kl} = \sum \limits _{l} \omega ^{(j-k)l } = \sum \limits ^{n-1}_{l} (\omega^{j-k}) ^{l}, $$ -\proof souèin -$$\Omega _{j} \Omega _{k} = \sum \limits ^{n-1}_{l=0} \Omega _{jl} \overline{\Omega _{kl}} = \sum \limits _{l} \omega ^{jl} \overline{\omega ^{kl}} = \sum \limits _{l} \omega ^{jl} \omega ^{-kl} = \sum \limits _{l} \omega ^{(j-k)l } = \sum \limits ^{n-1}_{l} (\omega^{j-k}) ^{l} $$ -Proto¾e $ \overline{\omega^{kl}} = \overline{\omega} ^{kl} = {({1 \over \omega} )}^{kl} = \omega ^{-kl}$. +proto¾e $ \overline{\omega^{kl}} = \overline{\omega} ^{kl} = {({1 \over \omega} )}^{kl} = \omega ^{-kl}$. \itemize\ibull -\: Pokud $j\neq k$, pou¾ijeme vzoreèek pro souèet geometrické posloupnosti, kde $a_{1}=1$ a $q=\omega ^{(j-k) }$ a dostaneme ${{\omega^{(j-k)n} -1} \over {\omega^{(j-k)} -1}} ={1-1 \over @ -1} = {0 \over \neq 0} = 0$ +\:Pokud $j\neq k$, pou¾ijeme vzoreèek pro souèet geometrické posloupnosti, kde $a_{1}=1$ a $q=\omega ^{(j-k) }$ a dostaneme ${{\omega^{(j-k)n} -1} \over {\omega^{(j-k)} -1}} ={1-1 \over @ -1} = {0 \over \neq 0} = 0$. -\: Pokud $j=k \sum \limits ^{n-1}_{l=0} (\omega ^{0}) ^{l} = n$. +\:Pokud $j=k \sum \limits ^{n-1}_{l=0} (\omega ^{0}) ^{l} = n$. \endlist \qed -a nyní slibované a u¾ i dokázané lemma - -\s{Lemma:} $\Omega _{j} . \Omega _{k} =$ +\>A nyní slibované a u¾ i dokázané lemma: -\itemize\ibull -\: $0$ pro $j\neq k$ - -\: $1$ pro $j=k$ -\endlist +\s{Lemma:} \quad $\Omega _{j} \cdot \Omega _{k} = \left\{ +{\displaystyle 0 \ldots j\neq k}\atop +{\displaystyle 1 \ldots j=k} +\right.$. -\s{Dùsledek:}$$\Omega*\overline{\Omega} = nE $$ +\s{Dùsledek:} \quad $\Omega \cdot \overline{\Omega} = nE$. -\>Jedná se o skalární souèin (jako pøedtím, èile prvek na pozici $ij$ je $0$ nebo $n$) $=>\Omega^{-1} = {1 \over n} \overline{\Omega}$ +\>Jedná se o skalární souèin (jako pøedtím, èili prvek na pozici $ij$ je $0$ nebo $n$) $\Rightarrow\Omega^{-1} = {1 \over n} \overline{\Omega}$. -\>na¹li jsme inverzi +\>Na¹li jsme inverzi: -$\Omega({1 \over n} \overline{\Omega}) = {1 \over n}\Omega*\overline{\Omega} = E$ +$\Omega({1 \over n} \overline{\Omega}) = {1 \over n}\Omega \cdot \overline{\Omega} = E$, \quad +$\Omega^{-1}_{jk} = {1 \over n}\overline{\omega^{jk}} = {1 \over n}\omega^{-jk} = {1 \over n} {(\omega^{-1})}^{jk}$, \quad +kde $\omega^{-1}$ je $\overline{\omega}$. -$\Omega^{-1}_{jk} = {1 \over n}\overline{\omega^{jk}} = {1 \over n}\omega^{-jk} = {1 \over n} {(\omega^{-1})}^{jk} $ -kde $\omega^{-1}$ je $\overline{\omega}$ +\>Ná¹ algoritmus poèítá tedy i inverzní transformaci, pouze místo $\omega_n$ pou¾ijeme $\overline{\omega_n}$ a vydìlíme $n$. Co¾ je skvìlé -- staèí znát pouze jeden algoritmus u~kterého staèí v~jednom pøípadì pou¾ít jinou matici a vydìlit $n$. - -\>Ná¹ algoritmus poèítá tedy i inverzní transformaci, akorát místo $\omega_n$ pou¾ijeme $\overline{\omega_n}$ a vydìlíme $n$. Co¾ je skvìlé - staèí znát pouze jeden algoritmus u kterého staèí v jednom pøípadì po¾ít jinou matici a vydìlit $n$! - -\s{Vìta:} pro $n= 2^k$ lze $DFT$ na $C^n$ spoèítat v èase $O(n \log n)$ a $DFT^{-1}$ takté¾ +\s{Vìta:} Pro $n= 2^k$ lze DFT na ${\bb C}^n$ spoèítat v~èase $\O(n \log n)$ a DFT$^{-1}$ takté¾. \s{Dùsledek:} -Polynomy stupnì $n$ lze násobit v èase $O(n \log n)$. - -$O(n \log n)$ pro vyhodnocení, $O(n)$ pro vynásobení a $O(n \log n)$ pro pøevedení zpìt +\>Polynomy stupnì $n$ lze násobit v èase $\O(n \log n)$: +$\O(n \log n)$ pro vyhodnocení, $\O(n)$ pro vynásobení a $\O(n \log n)$ pro pøevedení zpìt. \s{Pou¾ití:} \itemize\ibull -\: zpracování signálu - rozklad na $\sin$ a $\cos$ o rùzných frekvencích $=>$ spektrální rozklad -\: JPEG -\: násobení dlouhých èísel v èase $O(n \log n)$ +\:Zpracování signálu -- rozklad na siny a cosiny o~rùzných frekvencích $\Rightarrow$ spektrální rozklad. +\:JPEG. +\:Násobení dlouhých èísel v èase $\O(n \log n)$. \endlist \figure{img.eps}{Pøíklad prùbìhu algoritmu na vstupu velikosti 8}{3in} -Je to schéma zapojení kombinaèního obvodu (tzv. "motýlek") +\>To je schéma zapojení kombinaèního obvodu (tzv. \uv{motýlek}). \s{Z toho:} \itemize\ibull -\: kombinaèní obvod pro DFT - s $O(\log n)$ hladinami - a $O(n)$ hradly na hladinì -\: nerekurzivní algoritmus (postupujeme z leva) v èase $O(n \log n)$ - -èísla vstupu jsou èísla v binárním tvaru 0-7 pøeètená pozpátku +\:Kombinaèní obvod pro DFT + s~$\O(\log n)$ hladinami + a $\O(n)$ hradly na hladinì. +\:Nerekurzivní algoritmus (postupujeme zleva) v~èase $\O(n \log n)$. + Èísla vstupu jsou èísla v~binárním tvaru pøeètená pozpátku. \endlist