Użytkownik "pbartosz" <b...@g...com> napisał
>Mam problem ze zrozumieniem istoty szybkości algorytmu FFT.
>Moje wątpliwości opisałem tutaj:
>http://matematyka.pl/219308.htm
>Proszę o wytłumaczenie, najlepiej w odniesieniu do przykładu dla
>n=8.

Normalnie, tzn z najprostszej definicji DFT, jakbys chcial policzyc
wszystkie 8 skladowych, to w kazdej masz 8 skladnikow sumy,
czyli razem 64 skladniki do wyliczenia i zsumowania.

A tak jak opisales - obliczasz osobno skladniki parzyste i
nieparzyste, razem 8. Dodajesz je do siebie odpowiednio. I wlasnie
odwaliles 1/3 roboty. Bo wystarcza jeszcze dwa podobne kroki i masz
transformate policzona.

Bo jak mozesz zauwazyc - te sumy parzyste i nieparzyste ktore
wymieniles, sa znow bardzo podobnym wzorem zapisane,
i mozna je obliczac w analogiczny sposob.

Razem odpowiednio sprytny algorytm liczy to jeszcze zgrabniej i
mnozen jest ciut mniej.

J.