토픽 90 / 92·비교표
계산 기하, 수치 연산, 문자열 매칭
FFT vs DFT vs NTT
| 항목 | FFT | DFT | NTT |
|---|---|---|---|
| 시간 | O(n log n) | O(n^2) | O(n log n) |
| 연산 | 분할정복 | 직접 계산 | 정수/모듈로 |
| 정밀도 | 부동소수점 오차 | 정확 | 정확 (정수) |
| 적용 | 신호처리, 다항식 곱 | 이론/교육 | 암호학, 큰 수 곱 |
| 항목 | FFT | DFT | NTT |
|---|---|---|---|
| 시간 | O(n log n) | O(n^2) | O(n log n) |
| 연산 | 분할정복 | 직접 계산 | 정수/모듈로 |
| 정밀도 | 부동소수점 오차 | 정확 | 정확 (정수) |
| 적용 | 신호처리, 다항식 곱 | 이론/교육 | 암호학, 큰 수 곱 |