FFT에서
짝홀나눠서 계산횟수를 줄여서 DFT를 빨리계산하는거잔아
근데 내가 멍청해서그런데 일단 첫번째로 짝홀나누면
계산과정이 주는것은 알겠고 더 줄이면 계속 줄어드는것은알겠는데 이 계산과정을 다 전부 더하면
말그대로 마지막에 O (log)계산과정까지 다 더하면 원래 DFT계산보다 더 줄어드는지 어떻게암?
짝홀나눠서 계산횟수를 줄여서 DFT를 빨리계산하는거잔아
근데 내가 멍청해서그런데 일단 첫번째로 짝홀나누면
계산과정이 주는것은 알겠고 더 줄이면 계속 줄어드는것은알겠는데 이 계산과정을 다 전부 더하면
말그대로 마지막에 O (log)계산과정까지 다 더하면 원래 DFT계산보다 더 줄어드는지 어떻게암?
시간 복잡도가 줄어드는거지 네다섯개 하는데 필요한 연산수가 더 줄어드는건 아님. DFT 계수 한번 구하는데 O(N)연산이고 계수 N개 있으니 실제 DFT 전체 돌리는 계산은 O(N^2)이 되는데 FFT는 O(Nlog N)이니 후자가 빠르지.. (뭐 말은 O로 썼지만 실제론 Omega기도 하니까..)
시간복잡도랑 연산횟수가줄어들어서 빨리연산하는거아님? 그리고 짝홀로 나누고 또 그 짝수중에 거기서 짝홀로나누고 이러잔아 데이터가 N개라하면 N/2개의 푸리에계수연산만구하면 복소수 주기성에의해 나머지 푸리에계수는 어렵지않게구할수있는거고 또 그러면 N/2개의 짝수에서 또 짝홀각각 N/4 N/4로 나누면 또
N/4 푸리에변환 계수를 쉽게 구하는거고
근데 시간복잡성이라는게 연산수랑 같은거 아님?
근데 첫번째 스텝에 이미 푸리에 계수를 구했는데 계속 분해해서 연산을 수행하면 알고리즘에 있어서 그 스텝에 계산횟누는 줄겠지만 전체 연산횟수는 줄어드는지 그게 궁금함
다 더해서 나오는 복잡도가 N log N인가
인거임
그래? 내가 공부한 책으로는 계산과정을 계속 반복하다가 나머지가 O(NlogN)인걸로 알고 있는데 알고리즘을 반복해서 나오는 거로 알고 있는데.... 첫번째 스텝부터 푸리에 계수 구하라고 하던데.....
계산과정을 반복한다는게 니가 말하는 모든 계산과정을 다 합치는거랑 같은 뜻이야 계산복잡도를 N이라하면 f(N)=N + 2f(N/2) = ... 이런꼴로 나오는걸 다 계산한결과가 그거라구
그러니까 니말은 첫번째 계산과정이 (N/2)^2+N 이고 또 두번째 계산할때가 (N/4)^2/2+2N 세번째 계산할때가 (N/8)^2/4+3N 쭉쭉 이렇게 한게 계산을 더한거고 마지막 r번째과정이라면 rN+Nog(N) 이된다면 시간복잡성이 O(NLog(N))이 된다 이거지? NLog(N)이 데이터가 커질수록 aN보다 훨씬 커지니까
ㅇ 실제론 수가 작을때는 저런 알고리즘 안쓰고 걍 처리하는데, 그만큼 수가 작아질때까지 내려가는 횟수를 알고있고 이걸 고려했을때 연산이 N logN보다 작으니까 걍 O(N log N)으로 끝낼수 있는거
ㅇㅋ
뭐 하나만 묻자 무슨책으로 공부했냐? 이거 나도좀 책보고 제대로 공부해야할것같ㄷ. 수치해석책으로 공부했는데 영 나랑 안맞음
수치해석은 Ford?꺼로 했던거 같고 FFT는 다른 강의에서 들었음 참고교재로 Modern Computer Algebra를 넣어놓긴했네
전에 얘기한게 그거였구나
(a+b+c)*(p+q+r)을 계산하는 데에는 5번의 연산이 필요하지만, a*p+...을 계산하는 데에는 17번의 연신이 필요하지. 이걸 몰랐는지는 모르겠지만.