某些算法时间复杂性的下界

本文定义了两类机器,并讨论了在这两类机器上完成某类作业所需时间的下界。其中包括:在n个排好序的有理数中同时查询n个数至少需时cn log n;把n个有理数按大小排列分类至少需时cn log n,其中c为某个常数。