查看文章

In a general sequential model of computation, no restrictions are placed on the way in which the computation may proceed, except that parallel operations are not allowed. We show that in such an unrestricted environment TIME⋅ SPACE= Ω (N2/log N) in order to sort N integers, each in the range [1, N2].