We analyze how the choice of the sampling weight affects efficiency of the Monte Carlo evaluation of classical time autocorrelation functions. Assuming uncorrelated sampling or sampling with constant correlation length, we propose a sampling weight for which the number of trajectories needed for convergence is independent of the correlated quantity, dimensionality, dynamics, and phase-space density. By contrast, it is shown that the computational cost of the “standard” algorithm sampling from the phase-space density may scale exponentially with the number of degrees of freedom. Yet, for the stationary Gaussian distribution of harmonic systems and for the autocorrelation function of a linear function of phase-space coordinates, the computational cost of this standard algorithm is also independent of dimensionality.