質問

In the proof of simulation theory : simulating concurrent write : "a p-processors in a crcw algorithm can be no more then log(p)time faster then the best erew algorithm for the same problem"

enter image description here

can anyone explain me why it takes only log(p) to sort the array by the first component in the simulation proof and not O(plogp)?

役に立ちましたか?

解決

The sorting is accomplished in parallel with a log-depth sorting network. The AKS construction is a good example of a galactic algorithm. Batcher's bitonic sorting network with depth log^2 n is more reasonable in practice.

ライセンス: CC-BY-SA帰属
所属していません StackOverflow
scroll top