把时间切成频率

import cmath
import math


def fft(x):
    n = len(x)

    if n == 1:
        return [complex(x[0])]

    if n == 0 or n & (n - 1):
        raise ValueError("长度必须是2的正整数次幂")

    # 递归处理偶数与奇数编号的采样点
    even = fft(x[0::2])
    odd = fft(x[1::2])

    result = [0j] * n

    for k in range(n // 2):
        w = cmath.exp(-2j * math.pi * k / n)
        t = w * odd[k]

        # 蝶形运算
        result[k] = even[k] + t
        result[k + n // 2] = even[k] - t

    return result


def dft(x):
    n = len(x)

    return [
        sum(
            x[t] * cmath.exp(-2j * math.pi * k * t / n)
            for t in range(n)
        )
        for k in range(n)
    ]


N = 64
signal = [
    math.sin(2 * math.pi * 3 * n / N)
    + 0.6 * math.sin(2 * math.pi * 11 * n / N)
    for n in range(N)
]

fast_result = fft(signal)
slow_result = dft(signal)

error = max(
    abs(a - b)
    for a, b in zip(fast_result, slow_result)
)

print("FFT与DFT的最大差异:", error)

for k in range(1, N // 2):
    amplitude = 2 * abs(fast_result[k]) / N

    if amplitude > 0.1:
        print(f"频率 {k} Hz, 振幅 {amplitude:.3f}")

频率 3 Hz, 振幅 1.000
频率 11 Hz, 振幅 0.600