Let us assume that we have a classical function $f:\{0\,;\,1\}^n\to\{0\,;\,1\}^m$ which is efficiently computable. Then, its oracle is defined with $\mathbf{U}_f\,|x\rangle\,|y\rangle=|x\rangle\,|y\oplus f(x)\rangle$. I quite often read that if $f$ is efficiently computable, then so is $\mathbf{U}_f$. Why is it the case? Where is the computational cost of evaluating $f$ taken into account?
Since $\mathbf{U}_f$ is a permutation matrix, one can implement it with at most $2^{n+m}$ SWAP gates, but this is not very efficient. What am I missing?
Another related question is: given a permutation matrix, how can one find the appropriate CNOT/SWAP gates succession to implement it? Even if an efficient solution exists, how does one find it?