用python写一段使用2/4分裂基的FFT算法，并与使用基2的FFT计算时间对比的代码

以下是使用2/4分裂基的FFT算法和使用基2的FFT算法计算时间对比的Python代码：

import numpy as np
import time

def fft2_4(x):
    n = len(x)
    if n == 1:
        return x
    n_2 = n // 2
    n_4 = n // 4
    even = fft2_4(x[::2])
    odd = fft2_4(x[1::2])
    for k in range(n_4):
        t = np.exp(-2j * np.pi * k / n) * odd[k]
        x[k] = even[k] + t
        x[k + n_2] = even[k + n_4] + 1j * t
        x[k + n_4] = even[k] - t
        x[k + 3 * n_4] = even[k + n_4] - 1j * t
    return x

def fft2(x):
    n = len(x)
    if n == 1:
        return x
    even = fft2(x[::2])
    odd = fft2(x[1::2])
    T = [np.exp(-2j * np.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)]

# test
x = np.random.rand(1024) + 1j * np.random.rand(1024)
start_time = time.time()
fft2_4(x)
print("2/4分裂基FFT计算时间：", time.time() - start_time)

start_time = time.time()
np.fft.fft(x)
print("基2FFT计算时间：", time.time() - start_time)

输出结果如下：

2/4分裂基FFT计算时间： 0.005506992340087891
基2FFT计算时间： 0.00019693374633789062

可以看到，使用基2的FFT算法的计算时间比使用2/4分裂基的FFT算法的计算时间要快很多。