丁克诠.随机置换的分量与单调重新构组问题的计算等价性(英文)[J].数学研究及应用,1991,11(1):1~8 |
随机置换的分量与单调重新构组问题的计算等价性(英文) |
Computational Equivalence Between the Problems of Sorting and Monotone Reconstruction for Random Permutations |
|
DOI:10.3770/j.issn:1000-341X.1991.01.001 |
中文关键词: |
英文关键词: |
基金项目: |
|
摘要点击次数: 2249 |
全文下载次数: 1059 |
中文摘要: |
|
英文摘要: |
In this note, it is shown that the monotone reconstruction problem is equi-valent to that of sorting, in the sense of computational complexity. In particular from any given sorting algorithm A, an algorithm B for the monotone reconstruc-tion problem can be developed with at most O(m) time and O( m) space cost more than that used in A, and vice versa. As a consequence of this result, it is obtai-ned that the time complexity of the monotone reconstruction problem of n-ele-ment random permutations is O(nlogn). |
查看全文 查看/发表评论 下载PDF阅读器 |