Блог пользователя kevbamboo

Автор kevbamboo, история, 2 года назад, По-английски

Hi -is-this-fft-, yes this is fft.

I'm taking an algorithms class and we did some fft last week. I know it allows us to do polynomial multiplication in nlog(n) (which was what we were talking about) but I'm still a bit confused. If possible, could you give an easy explanation (with a little bit of math though)?

  • Проголосовать: нравится
  • -34
  • Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

It's better to ask your classmate or professor, as a random codeforces user probably won't know what exactly was taught at your class.

»
2 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

I don't believe there is any "easy" explanation. It will take an entire lecture to teach FFT (I've tried) and there really isn't any reasonable way to make it shorter, especially since I have no idea which part you are confused about. I would basically need to write an entire lecture here and there's no reason to expect I'd do it any better than the various lectures and tutorials that already exist online.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I think these notes explain it pretty well.