Jestem na pierwszym roku matematyki więc byłbym wdzięczny gdyby ktoś pomógł mi używając metod dostępnych dla mnie
Jeśli liczba \(\displaystyle{ n>1}\) jest podzielna przez \(\displaystyle{ m>1}\), to zadanie obliczenia dyskretnej transformaty Fouriera ciągu liczb (zespolonych) \(\displaystyle{ a_{0}, . . . , a_{(n-1)}}\) można sprowadzić do obliczenia m transformat podciągów o długości \(\displaystyle{ \frac{n}{m}}\), a następnie do obliczenia wyniku kosztem \(\displaystyle{ c(m-1)n}\) działań arytmetycznych \(\displaystyle{ (c = const)}\). Dla \(\displaystyle{ n=1}\) koszt obliczenia transformaty jest zerowy.
a) Rozwiązując odpowiednie równanie róznicowe, wyznacz koszt obliczenia transformaty dla
\(\displaystyle{ n=2^{k}}\) i \(\displaystyle{ m=2}\).
b) Przypuśćmy, ze liczba n jest podzielna przez 4. Majac dane 4 transformaty odpowiednich podciagów o długości \(\displaystyle{ \frac{n}{4}}\), można obliczyć transformatę całego ciagu danego, obliczajac najpierw dwie transformaty podciągów o długości \(\displaystyle{ \frac{n}{2}}\), a następnie końcowy wynik, albo można obliczyć końcowy wynik bezpośrednio na podstawie tych czterech transformat podciągów. Która metoda wymaga wykonania mniejszej liczby działań? Odpowiedz uzasadnij.