Average running time of the fast Fourier transform |
| |
Authors: | Persi Diaconis |
| |
Institution: | 1. Bell Laboratories, Murray Hill, New Jersey, USA;2. Stanford University, Stanford, California, USA |
| |
Abstract: | We compare several algorithms for computing the discrete Fourier transform of n numbers. The number of “operations” of the original Cooley-Tukey algorithm is approximately 2nA(n), where A(n) is the sum of the prime divisors of n. We show that the average number of operations satisfies . The average is not a good indication of the number of operations. For example, it is shown that for about half of the integers n less than x, the number of “operations” is less than n1.61. A similar analysis is given for Good's algorithm and for two algorithms that compute the discrete Fourier transform in O(n log n) operations: the chirp-z transform and the mixed-radix algorithm that computes the transform of a series of prime length p in O(p log p) operations. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|