节点文献
某些算法时间复杂性的下界
【摘要】 本文定义了两类机器,并讨论了在这两类机器上完成某类作业所需时间的下界。其中包括:在n个排好序的有理数中同时查询n个数至少需时cn log n;把n个有理数按大小排列分类至少需时cn log n,其中c为某个常数。
- 【文献出处】 中国科学 ,Science in China,Ser.A , 编辑部邮箱 ,1979年05期
- 【下载频次】43
【摘要】 本文定义了两类机器,并讨论了在这两类机器上完成某类作业所需时间的下界。其中包括:在n个排好序的有理数中同时查询n个数至少需时cn log n;把n个有理数按大小排列分类至少需时cn log n,其中c为某个常数。