python - Cooley-Tukey 算法 python 超出范围

Question

我正在分析用 Python 编写的 Cooley-Tukey 算法实现的复杂性(代码取自 here):

def fft(x):
N = len(x)
print N, N//2
if N <= 1:
    return x
even = fft(x[0::2])
odd = fft(x[1::2])
T = [exp(-2j*pi*k/N)*odd[k] for k in range(N//2)]
return [even[k] + T[k] for k in range(N//2)] + [even[k] - T[k] for k in range(N//2)]

该代码与网页中显示的示例配合得很好；事实上，它似乎适用于任何长度 <= 9 的列表。出于某种原因，尝试使用长度 > 10 的列表:

print( ' '.join("%5.3f" % abs(f) for f in fft([0,1,2,3,4,5,6,7,8,9])))

返回以下错误:

T = [exp(-2j*pi*k/N)*odd[k] for k in range(N//2)]

IndexError: list index out of range

有谁知道失败的原因吗？

Answer 1

您使用的 Cooley-Tukey 实现假设输入长度是 2 的幂。二次幂输入长度是迄今为止最容易实现 Cooley-Tukey 的；将此代码扩展到非二次方输入长度需要完全重写它。