Брза Фуријеова трансформација — разлика између измена

'''Брза Фуријеова трансформација''' ({{јез-ен|Fast Fourier transformation}}; често се означава као -{FFT}-) је [[алгоритам]] за "брзо" израчунавање вредности [[дискретна Фуријеова трансформација|дискретне Фуријеове трансформације]]. Убрзање у односу на уобичајен поступак израчунавања дискретне Фуријеове трансформације постиже се избегавањем поновног израчунавања израза који се међусобно негирају. Алгоритам се приписује [[Џејмс В. Кули|Џејмсу В. Кулију]] (-{James W. Cooley}-) и [[Џон В. Туки|Џону В. Тукију]] (-{John W. Tukey}-) који су га објавили [[1965]]. године. Међутим, [[Карл Фридрих Гаус]] га је развио већ 1805. да би израчунао путању астероида [[Палас]] и [[Јуно]]. ПритомПри том су многе верзије развијене и пре Кулијеве и Тукијеве варијанте. После су се појавила многа побољшања и варијације.

ДФТ израчунавамо тако што наше тачке (вектор) прво поделимо на два вектора, један који одговара компонентама изворног вектора са парним индексима, а други са непарним. Онда израчунамо ДФТ оба вектора и спојимо резултате. ПритомПри том користимо особине јединичног корена Фуријеове матрице. После понављамо [[рекурзија|рекурзивно]] поступак. Тиме можемо да ДФТ на крају израчунамо према сложености <math>O( \log(n) )</math> у времену.