dft – Non-uniform FFT – Signal Processing Stack Exchange

This is a common problem, but the best choice depends a lot on your requirements: Do you need amplitude, phase, or both, do you want to do frequency domain processing, does the transform needs to be information preserving and/or invertible, do you need to smooth to combine the “low density” frequency areas, etc?

What algorithms come into play?

Constant Q transform, wavelets, cascaded half-band filters, third (or 1/N) octave band analyzers, etc.

Are they as computational effective as the FFT?

Generally not. Many of these algorithms use internally an FFT (or related transform) and then employ a post processing step to recalculate whatever you want to calculate.