Пусть N = PQ. Этот представляет собой более общий случай, чем рассмотренный в предыдущей главе. Теперь не требуется, чтобы
P или Q были степенями двойки.
Напомним основную формулу:
(1).
Рассмотрим формулу:
(41).
Эта формула эквивалентна формуле (1). В самом деле:
Двойная сумма по pQ + q - это все равно, что одинарная сумма по n, просто
порядок слагаемых другой.
Вернемся к формуле (41). В скобках там стоит обычное прямое БПФ, только не для всех xn,
а для последовательности из P штук, взятых с шагом Q. Количество последовательностей равно Q.
Элементы последовательности выбираются формулой xpQ + q, где p - номер элемента,
q - номер последовательности.
Пусть мы умеем вычислять БПФ для P элементов за время Z(P). Нам понадобится вычислить Q
таких БПФ, на что потратим время O(QZ(P)). Тем самым мы получим все множители в скобках из формулы (41).
После этого надо будет вычислить N элементов Xk, каждый из которых
потребует O(Q) действий, итого потребуется еще O(NQ) действий, а в сумме -
O(QZ(P) + QN) действий.
В предыдущем алгоритме P - было степенью двойки, а для такого числа элементов мы умеем вычислять
БПФ за O(Plog2P) шагов, т.е. Z(P) = Plog2P, и получится
O(QZ(P) + QN) = O(QPlog2P + QN) = O(Nlog2P + N2/P) действий.
Тем самым, мы несколько более простым путем получим ту же оценку сложности алгоритма.
Если P - не степень двойки, мы умеем вычислять ПФ за O(P2) шагов,
т.е. Z(P) = P2, и получится
O(QZ(P) + QN) = O(QP2 + QN) = O(N2/Q + N2/P) действий.
Если P и Q достаточно велики, это лучше, чем O(N2).
Знаете ли Вы, что электромагнитное и другие поля есть различные типы колебаний, деформаций и вариаций давления в эфире.
Понятие же "физического вакуума" в релятивистской квантовой теории поля подразумевает, что во-первых, он не имеет физической природы, в нем лишь виртуальные частицы у которых нет физической системы отсчета, это "фантомы", во-вторых, "физический вакуум" - это наинизшее состояние поля, "нуль-точка", что противоречит реальным фактам, так как, на самом деле, вся энергия материи содержится в эфире и нет иной энергии и иного носителя полей и вещества кроме самого эфира.
В отличие от лукавого понятия "физический вакуум", как бы совместимого с релятивизмом, понятие "эфир" подразумевает наличие базового уровня всей физической материи, имеющего как собственную систему отсчета (обнаруживаемую экспериментально, например, через фоновое космичекое излучение, - тепловое излучение самого эфира), так и являющимся носителем 100% энергии вселенной, а не "нуль-точкой" или "остаточными", "нулевыми колебаниями пространства". Подробнее читайте в FAQ по эфирной физике.