¿Puede alguien revisar mi pregunta sobre la complejidad FFT?

Answer 1

‘FFT’ es en realidad un acrónimo aplicable a toda una familia de algoritmos de transformación rápida. Pero la mayoría de ellos asume una potencia de 2 para el número de puntos, mientras que tendrás que hacer varios de ellos para parchear juntos en una convolución 3D. Pero siempre que pueda elegir el tamaño de cada transformación como una potencia de 2, o rellenar los datos de la ventana sin degradarlos para poder utilizar una potencia de 2, entonces la FFT será mucho más rápida que una convolución, a menos que tiene un hardware especializado que puede hacer la convolución más rápidamente, como una GPU moderna. BTW: ¿te refieres a convolving una matriz 3 × 3 con una “imagen Full HD”? ¿Vas a deslizar la matriz 3 × 3 a lo largo de la imagen? En ese caso, no tiene mucho sentido convulsionarlo con la imagen completa en un momento dado. ¿Y estás haciendo una convolución discreta o una circular? Hay una gran variedad de algoritmos rápidos para este último: la FFT es la más conocida, pero no la única.