Mesh sorting and selection optimal on the average

被引：0
|
作者：
Chlebus, BS
机构：
来源：
COMPUTERS AND ARTIFICIAL INTELLIGENCE | 1997年 / 16卷 / 02期
关键词：
parallel algorithm; mesh-connected computer; average performance; optimal algorithm; sorting; selection;
D O I：
暂无
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ; 0812 ; 0835 ; 1405 ;
摘要：
We consider 1-1 sorting and selection problems on an n x n mesh-connected processor arrays. Algorithms are developed which are fast with respect to the average-time performance. We show that selection can be accomplished in the average time n + o(n), and sorting in the average time 2.n + o(n). Matching lower bounds are also proved.
引用
收藏
页码：141 / 152
页数：12
相关论文
共 50 条
12345