【摘要】 对于一个 ｍ ×ｎ（ｍ ≤ｋ）的列有序矩阵，文中在 ｎ × ｎ 可重构造的网孔机器上提出了一个并行 ｋ选择算法，其时间复杂度为 Ｏ（ｌｏｇ２ｍ ＋ ｌｏｇｍ ｌｏｇ２ ｎ＋ ｌｏｇ３ ｎ），而对于一般的ｌ元集，文中在相同的模型下提出了一个时间复杂度为 Ｏ ｌｏｇ２ ｌｎ ＋ ｌｏｇ ｌｎ ｌｏｇ２ ｎ＋ ｌｏｇ３ｎ＋ ｌｎ ｌｏｇ ｌｎ 的并行 ｋ选择算法．当时 ｌ≥ Ｏ（ｎｌｏｇ３ｎ／ｌｏｇ ｌｏｇｎ，该时间复杂度为 Ｏ ｌｎ ｌｏｇ ｌｎ ．特别地，当ｌ＝ Ｏ（ｎ１＋ ε）（ε＞ ０ 为常数），则时间复杂度为 Ｏ ｌｎ ｌｏｇｎ ．此时达到的加速比为 ｎ／ｌｏｇｎ．更多还原

【Abstract】 A paralle algorithm of n×n reconfigurable mesh is proposed in this paper,which selects the k\|th element in an m×n(m≤k) matrix with sorted columns.It runs in time O( log 2m+ log m log 2n+ log 3n), Also proposed is a parallel algorithm that selects the k\|th element in a general set with l elements on the same model.Its time complexity is O log 2ln+ log ln log 2n+ log 3n+ln log ln.When l≥O(n log 3 n/ loglog n),it becomes Oln log ln.Especially when l=O(n 1+ε )(ε>0 is a constant),it is Oln log n and the acceleration ratio of the algorithm in this situation is n /log n.更多还原