Overview

Minimalistic vector art of Knapsack problem with fruit

The Fast Fourier Transform (FFT) algorithm is a divide and conquer algorithm that computes the Discrete Fourier Transform (DFT) of a sequence, or its inverse (IDFT). The DFT is a linear transformation that maps a vector of complex numbers to another vector of complex numbers. The DFT is widely used in signal processing and related fields to analyze frequencies contained in a signal.

…