고속 푸리에 변환 (1) 썸네일형 리스트형 FFT Algorithm, Cooley-Tukey Algorithm 푸리에 변환은 다양한 곳에서 응용된다. 컴퓨터는 푸리에 변환 중 주기를 가진 이산 신호에 대해서만 푸리에 변환을 수행할 수 있다. DFT(Discrete Time Fourier Transform)는 다음과 같이 정의될 수 있을 것이다. 정의에 따라 푸리에 변환을 구하게 되면 O(N^2)의 시간이 걸리게 된다. 즉 신호의 주기가 길어질 수록 푸리에 변환을 얻기 위해 걸리는 시간은 주기 제곱에 비례하여 증가하게 되고, 이는 빨리 문제를 해결하고자 하는 우리 입장에서 바람직한 현상은 아니다. FFT Algorithm은 주기에 따라 제곱에 비례하여 증가하는 현상을 O(NlogN)까지 개선할 수 있다. FFT의 기본적인 컨셉은 분할과 정복(Divide and Conquer)이다. 분할과 정복에 대해서 간단히 설명.. 이전 1 다음
