| A Unified O(log N) and Optimal Sorting Vector Algorithm |
| |
| 引用本文： | Gao Qingshi. A Unified O(log N) and Optimal Sorting Vector Algorithm[J]. 计算机科学技术学报, 1995, 10(5): 470-475. DOI: 10.1007/BF02948343 |
| |
| 作者姓名： | Gao Qingshi |
| |
| 作者单位： | TheInstituteofIntelligence,LanguageandComputerScience,BeijingUniversityofScienceandTechnology,Beijing |
| |
| 摘 要： | A unified vector sorting algorithm(VSA) is proposed,which sorts N arbitrary numbers with c log2 N-bits on an SIMD multi-processor system (SMMP) with p=N^1 ε/u processors and a composite interconnected network in T=c/ε(4 log2 N-2 log2 u 10u) time,where c is an arbitrary positive constant.When ε is an arbitrary small positive constant and u=log2 N,it is an O(log N) algorithm and p=N^1 ε/log2 N;when ε=1/log N and u=2 log2 N,it is an optimal algorithm (p=N/log2 N,T=O(log^2 N),pT=O(N log N));where u=1,c=1 and ε=0.5 (a constant).
|
| 关 键 词： | 多处理机系统 优化分类 向量算法 O（log N）算法 |
A unifiedO(logN) and optimal sorting vector algorithm |
| |
| Qingshi Gao. A unifiedO(logN) and optimal sorting vector algorithm[J]. Journal of Computer Science and Technology, 1995, 10(5): 470-475. DOI: 10.1007/BF02948343 |
| |
| Authors: | Qingshi Gao |
| |
| Affiliation: | The Institute of Intelligence; Language and Computer Science; Beijing University of Science and Technology; Beijing 100083; |
| |
| Abstract: | A unilied vector sorting algorithm (VSA) is proposed, which sorts N arbitrary num-bers with clog. N-bits on an SIMD multi-processor system (SMMP) with processors and a composite interconnected network in time, where c is an arbitrary positive constant. When is an arbitrary small posi-tive constant and u = log2 N, it is an O(logN) algorithm and when it is an optimal algorithm,pT = O(N log N)); where u = 1, c = 1 and e = 0.5 (a constant). |
| |
| Keywords: | Parallel processing sorting time complexity optimal algorithm multi-processor system |
| 本文献已被 CNKI 维普 SpringerLink 等数据库收录！ |
| 点击此处可从《计算机科学技术学报》浏览原始摘要信息 |
|
点击此处可从《计算机科学技术学报》下载免费的PDF全文 |
