Złożoność algorytmu

XYZmat
Użytkownik
Użytkownik
Posty: 142
Rejestracja: 1 wrz 2017, o 11:39
Płeć: Kobieta

Złożoność algorytmu

Post autor: XYZmat »

Mam takie zadanie:
Algorytm FFT na podstawie danego ciągu liczb zespolonych o długości n oblicza ciąg liczb zespolonych o długości \(\displaystyle{ n}\). Jeśli \(\displaystyle{ n = 1}\), to koszt tego obliczenia jest równy \(\displaystyle{ 0}\). Jeśli liczba n jest podzielna przez \(\displaystyle{ 3}\), to algorytm rozwiązuje \(\displaystyle{ 3}\) zadania dla ciągów o długości \(\displaystyle{ n/3}\), po czym „scala” wyniki w wynik końcowy, wykonując przy tym \(\displaystyle{ 3n}\) mnożeń zespolonych, które są operacjami dominującymi. Znajdź wzór opisujący złożoność obliczeniową algorytmu FFT dla zadań o rozmiarze \(\displaystyle{ n = 3k}\), gdzie \(\displaystyle{ k}\) jest liczbą naturalną, układając i rozwiązując odpowiednie równanie różnicowe.
Rozwiązanie:
Niech \(\displaystyle{ a _{n}}\) - koszt wykonania FFT dla ciągów o długości \(\displaystyle{ n}\) i \(\displaystyle{ a _{n}=3a _{(n/3)} +3n}\), \(\displaystyle{ b _{k}=a _{ 3^{k} }}\) - koszt wykonania FFT dla ciągów o długości \(\displaystyle{ n=3^{k}}\)
Mamy teraz: \(\displaystyle{ a _{ 3^{k} }=3a _{ 3^{k-1}}+3 \cdot 3^{k} }}\), \(\displaystyle{ b _{k}=3b _{k-1}+3 \cdot 3^{k} }}\)
Rozwiązujemy równanie jednorodne: \(\displaystyle{ b_{k}=3b _{k-1}}\), przyjmując \(\displaystyle{ b_{k}=\lambda}\), co daje \(\displaystyle{ \lambda=3}\).
Stąd mamy rozwiązanie szczególne równania jednorodnego: \(\displaystyle{ b_{k}=c \cdot k \cdot 3^{k}}\), gdzie \(\displaystyle{ c}\) jest wielomianem stopnia \(\displaystyle{ 0}\).
To daje mi równanie: \(\displaystyle{ c \cdot k \cdot 3^{k}=3c(k-1)3^{k-1}+3^{k+1}}\), więc otrzymuję \(\displaystyle{ c=3}\)
Do tego momentu doszłam sama i rozumiem to, ale w rozwiązaniu, które otrzymałam widnieje po tym: \(\displaystyle{ a _{k}=d3^{k}+3 \cdot 3^{k}k\lambda=3}\), lecz nie rozumiem skąd się to bierze i mam wątpliwości, czy w ogóle te zadanie jest już skończone.
ODPOWIEDZ