OPTIMAL-ALGORITHMS FOR SORTING ON SINGLE TAPE TURING-MACHINES

被引：0
作者：
WIEDERMANN, J
机构：
来源：
IFIP TRANSACTIONS A-COMPUTER SCIENCE AND TECHNOLOGY | 1992年 / 12卷
关键词：
MODELS OF COMPUTATION; NONNUMERICAL ALGORITHMS AND PROBLEMS; SORTING;
D O I：
暂无
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
It is shown that on a single-tape deterministic Turing machine sorting of m integers, each of length l, is of time complexity THETA(ml log (m+2l-1/m)). Further, on nondeterministic off-line single-tape Turing machine sorting can be done in time 0(m3/2l), which by the recent results of Dietzfelbinger et al. cannot be improved in general.
引用
收藏
页码：306 / 314
页数：9
相关论文
共 4 条
  • [1] DIETZFELBINGER M, 1991, THEORET COMPUT SCI, P113
  • [2] Hopcroft J, 1975, 16 ANN S FDN COMP SC, P57
  • [3] STOSS HJ, 1973, ACTA INFORM, P80
  • [4] [No title captured]
1