A word RAM is a unit-cost random-access machine with a word length of w bits, for some ur, and with an instruction repertoire similar to that found in present-day computers. The simple lower bounds for the problems of...
详细信息
ISBN:
(纸本)3540642307
A word RAM is a unit-cost random-access machine with a word length of w bits, for some ur, and with an instruction repertoire similar to that found in present-day computers. The simple lower bounds for the problems of sorting and searching valid in the comparison-based model do not hold for the word RAM, so that the well-known algorithms for these tasks are not optimal for the word RAM. This paper gives an overview of faster algorithms known for sorting and searching on the word RAM, many of which were developed within the last few years.
We present a conservative CRCW parallel algorithm for integer sorting. This algorithm sorts n integers from {0,1,..., m-1} in time O(n log log min (m, n,)/P + using p processors. The simulation of our parallel algorit...
详细信息
ISBN:
(纸本)354060216X
We present a conservative CRCW parallel algorithm for integer sorting. This algorithm sorts n integers from {0,1,..., m-1} in time O(n log log min (m, n,)/P + using p processors. The simulation of our parallel algorithm on the sequential machine yields a sequential algorithm for integer sorting which sorts n integers from {0,1,..., m-1) in time O(n min (log log n, log (log m/log n)).
暂无评论