用Python语言写一个FT算法程序

好的，以下是一个Python实现的FT算法程序：

import math

def FT(x):
    N = len(x)
    if N == 1:
        return x
    else:
        X_even = FT(x[0::2])
        X_odd = FT(x[1::2])
        X = [0] * N
        for k in range(N//2):
            X[k] = X_even[k] + X_odd[k] * math.e**(-2*math.pi*1j*k/N)
            X[k+N//2] = X_even[k] - X_odd[k] * math.e**(-2*math.pi*1j*k/N)
        return X

其中，这个FT函数实现了递归计算FFT，并返回FFT计算结果。输入参数x是一个长度为N的实数序列，输出结果是一个长度为N的复数序列。在这个函数中，我们使用了Python中的切片操作，`x[0::2]`表示从序列x中取出下标为偶数的元素，而`x[1::2]`则表示从序列x中取出下标为奇数的元素。

这个程序的时间复杂度为O(NlogN)。