No.
Intuitively, we don't use properties of the oracle $U_f$, we're just making a quantum tomography of a state which equals $|\psi_f\rangle = \frac{1}{\sqrt{N}}\sum_i (-1)^{f(i)}|i\rangle$ for some $f$ (and there are $N$ possible $f$).
Let's also denote $|\psi_0\rangle = \frac{1}{\sqrt{N}}\sum_i |i\rangle$.
One can use the proof of Grover's algorithm optimality to derive the bound on the number of copies needed for tomography.
There is an inequality which gives
$$
2N-2\sqrt{N}\sqrt{p} - 2\sqrt{N}\sqrt{N-1}\sqrt{1-p} \le
$$
$$
\le \sum_f ||\psi_{f}\rangle^{\otimes K} - |\psi_{0}\rangle^{\otimes K}|^2,
$$
for the average success probability $p$ of determining $f$ from $K$ copies of $|\psi_{f}\rangle$.
But
$$
\langle \psi_0 | \psi_f \rangle = \frac{N-2}{N},
$$
and
$$
||\psi_{f}\rangle^{\otimes K} - |\psi_{0}\rangle^{\otimes K}|^2 = 2-2{\rm Re}\langle \psi_0 | \psi_f \rangle^K,
$$
so that
$$
2N - 2\sqrt{N} \le N(2 - 2 (\frac{N-2}{N})^K),
$$
if we want $p$ to be close to 1.
Thus
$$
\frac{1}{\sqrt{N}} \ge (\frac{N-2}{N})^K \ge 1-\frac{2K}{N} ,
$$
hence
$$
K \ge (N-\sqrt{N})/2,
$$
which means the complexity is $O(N)$ at least.
