Ho letto che per calcolare la convoluzione di due segnali x, y (1D per esempio), il metodo ingenuo prende O(NM).
Tuttavia FFT è usato per calcolare FFT^-1(FFT(x)FFT(y)), che prende O(N log(N)), nel caso in cui N> M.
Mi chiedo perché questa complessità sia considerata migliorerispetto a quello precedente, poiché M non è necessariamente più grande di log (N). Inoltre, M è molto spesso la lunghezza di un filtro, che non scala con il segnale da filtrare, e in realtà ci fornisce una complessità più simile a O(N) rispetto a O(N^2).
risposte:
2 per risposta № 1La convoluzione veloce nel dominio della frequenza èin genere più efficiente della convoluzione diretta quando la dimensione del filtro supera una soglia specifica. Quindi per i filtri relativamente piccoli la convoluzione diretta è più efficiente, mentre per i filtri più lunghi arriva un punto in cui la convoluzione basata su FFT è più efficiente. Il valore effettivo di m per questo "punto di svolta" dipende da molti fattori, ma in genere è compreso tra 10 e 100.