[알고리즘] Fast Fourier Transform - Githubissues

shinkeonkim / TIL

Today I Learned

0 stars 0 forks source link

[알고리즘] Fast Fourier Transform #18

Open shinkeonkim opened 3 months ago

shinkeonkim commented 3 months ago

고속 푸리에 변환(Fast Fourier Transform)은 convolution을 O(NlogN)의 시간복잡도로 구할 때 활용된다.

Q. 푸리에 변환은 뭘까? Q. convolution은 뭘까?

푸리에 변환은 함수를 함수를 함수로 보내는 변환이다.
PS에서의 푸리에 변환은 수열을 수열로 보내는 이산 푸리에 변환(Discrete Fourier Transform, DFT)이다.

뭔가 잘 이해가 안간다. 관련 영상을 찾는다. → https://www.youtube.com/watch?v=Mc9PHZ3H36M

보던 중에, 복소평면을 좀 더 이해를 하고 시작해야겠다 생각함.