Рассмотрим функцию generateSignal, которая реализует генерацию сигнала, представляющего сумму косинусоидальных функций с заданными частотами и амплитудами. Пусть заданы множества частот $\displaystyle{ f_1, f_2, \dots, f_m }$ и амплитуд $\displaystyle{ a_1, a_2, \dots, a_m }$. Для каждого дискретного момента времени $\displaystyle t_i = \frac{i}{SampleRate}$, где $\displaystyle i = 0, 1, \dots, N-1$ и $\displaystyle N = SampleRate \times duration$, вычисляется значение сигнала по формуле

$\displaystyle x(t_i) = \sum_{j=1}^{m} a_j \cos\left( 2 \pi f_j t_i \right).$

Данный алгоритм имеет временную сложность $\displaystyle O(N \cdot m)$, так как для каждого из $\displaystyle N$ сэмплов выполняется сумма по $\displaystyle m$ слагаемым.

Переходя к функции dft, рассмотрим её цель – вычисление дискретного преобразования Фурье исходного сигнала. Для каждого индекса спектральной компоненты $\displaystyle k$, где $\displaystyle k = 0, 1, \dots, \frac{N}{2}-1$, вычисляются вещественная и мнимая части спектра по формулам

$\displaystyle X_{real}(k) = \sum_{n=0}^{N-1} x(n) \cos\left( \frac{2\pi k n}{N} \right),$ $\displaystyle X_{imag}(k) = - \sum_{n=0}^{N-1} x(n) \sin\left( \frac{2\pi k n}{N} \right).$

Амплитуда спектральной компоненты определяется как

$\displaystyle A(k) = \frac{\sqrt{X_{real}(k)^2 + X_{imag}(k)^2}}{N},$

а соответствующая частота вычисляется по формуле

$\displaystyle f(k) = \frac{k \cdot SampleRate}{N}.$

При выполнении данной функции используется двойной цикл: внешний цикл по $\displaystyle k$ (около $\displaystyle N/2$ итераций) и внутренний цикл по $\displaystyle n$ (всего $\displaystyle N$ итераций), что приводит к временной сложности алгоритма $\displaystyle O(N^2)$. Данное соотношение существенно ограничивает применимость прямого алгоритма ДПФ при больших значениях $\displaystyle N$, поэтому в практических приложениях часто используется алгоритм быстрого преобразования Фурье (FFT) с временной сложностью $\displaystyle O(N \log N)$.

Докажем корректность вычисления спектра. Согласно определению дискретного преобразования Фурье, для сигнала $\displaystyle x(n)$ его спектральное представление определяется как

$\displaystyle X(k) = \sum_{n=0}^{N-1} x(n) e^{-2\pi i \frac{k n}{N}},$

что эквивалентно разложению на косинус и синус, где вещественная и мнимая части вычисляются вышеупомянутым образом. Нормировка на $\displaystyle N$ обеспечивает корректное масштабирование амплитуд, позволяющее сравнивать их с исходными значениями в сумме косинусоид. Таким образом, функция dft реализует точное математическое определение дискретного преобразования Фурье.

Оценка эффективности алгоритма основана на анализе вложенных циклов. Функция generateSignal требует $\displaystyle O(N \cdot m)$, где $\displaystyle m$ обычно невелико, а функция dft, в силу своей структуры, требует $\displaystyle O(N^2)$. При использовании частоты дискретизации порядка $\displaystyle 10^4$ и длительности сигнала в 1 секунду число операций в dft составляет порядка $\displaystyle 5 \times 10^7$, что является приемлемым для экспериментальных целей, но может стать узким местом при обработке более длительных сигналов. Вывод данных в CSV осуществляется за время, пропорциональное числу вычисленных спектральных компонент, что не оказывает существенного влияния на общую производительность алгоритма.

Таким образом, предложенная реализация строго соответствует математическим определениям дискретного преобразования Фурье, обеспечивает корректное вычисление спектрального представления сигнала и демонстрирует компромисс между вычислительной точностью и сложностью алгоритма.