国防科技大学计算机研究所
纸质出版:1995
移动端阅览
[1]杨利,吴涛,周兴铭.基于“反体存储器”概念的分类器:SORTER[J].电子学报,1995(02):7-11.
杨利, 吴涛, 周兴铭. SORTER:A Sorting Engine Based on"Negative Memory"Concept[J]. Acta Electronica Sinica, 1995, (2).
本文描述和分析了一个基于反体存储器概念模型的新型分类器(SORTER)的硬件结构和相应的分类算法。由于不是采用基于比较的分类方法,SORTER避免了常规分类算法O(nlogn)的时间下界。SORTER仅利用两种基本的读写操作实现数据元素的分类,按存储器访问次数计算,该算法的复杂度仅为O(n).此外,对SORTER算法稍加修改,就可以实现数据库中的多数运算,其时间的复杂性同样为O(n).SORTER基于常规的RAM技术,其结构和实现都不困难。
This paper describes the design and analysis of the architecture and the algorithms of a novel sorting engine-SORTER based on so called"Negative Memory"concept.Without performing any comparison
this SORTER avoids the O(n log n) lower bound constraint on ordinary sorting algorithms.SORTER uses only read and write
the two basic operations
to perform elements sorting.In terms of the number of memory access
SORTER achieves the complexity of O(n).In addition
using the fundamental sorting algorithm with slight modifications
SORTER can also be used for majority of database operations with complexity O(n).
0
浏览量
17
下载量
0
CSCD
关联资源
相关文章
相关作者
相关机构
京公网安备11010802024621