The naive implementation of an $N$-point DFT is basically a multiplication by a $N \times N$ matrix. This results in a complexity of $\mathcal{O}(N^2)$.
One of the most common Fast Fourier Transform (FFT) algorithm is the radix-2 algorithm. This is a basic divide and conquer approach. Let's note $W_N = e^{-j\frac{2\pi}{N}}$, then the DFT formula is given by $$X(k) = \sum_{n=0}^{N-1} x(n)W_N^{kn}.$$ The sum can then be divided in two sums as follows $$X(k) = \sum_{n=0}^{N-1} x(2n)W_N^{2kn} + \sum_{n=0}^{N-1} x(2n+1)W_N^{k(2n+1)}$$ where the first one deals with the even samples of $x(n)$ and the second one with the odd samples of $x(n)$. Noting $x_e(n) = x(2n)$ and $x_o(n) = x(2n+1)$ and using the fact that
- $W_N^{k(2n+1)} = W_N^{2kn}W_N^k$, and
- $W_N^{2kn} = W_{N/2}^{kn}$,
this can be re-written as $$ \begin{align} X(k) &= \sum_{n=0}^{N/2-1} x_e(n)W_{N/2}^{kn} + W_N^k\sum_{n=0}^{N/2-1} x_o(n)W_{N/2}^{kn} \\ & = X_e(k) + W_N^kX_o(k) \end{align} $$ where $X_e(k)$ and $X_o(k)$ are the $N/2$-point DFT transforms of the even and odd samples of $x(n)$ respectively. So we just transformed a single $N$-point DFT into two smaller $N/2$-point DFTs. We can then re-iterate the same process on those two smaller DFTs. This divide-and-conquer approach allows to reach complexity of $\mathcal{O}(N\log N)$, which is way better than the $\mathcal{O}(N^2)$ we had with the naive DFT implementation.