模擬理論 - 如何排序只有日誌（p）？

在模擬理論的證明：模擬併發寫：「在CRCW算法對處理器可再沒有其他日誌（p）的時間快的話，最好EREW算法同樣的問題，」模擬理論 - 如何排序只有日誌（p）？

任何人都可以解釋爲什麼它只需要log（p）按照仿真證明中的第一個組件排序數組，而不是O（plogp）？

2014-03-25 Ohad

我不熟悉你所說的證明或概念。請包括所有必要的信息。但我認爲這將更適合http://cs.stackexchange.com/ –

排序與日誌深度sorting network並行完成。 AKS構造是一個星系算法的好例子。 Batcher's bitonic sorting network與深度log^2在實踐中更合理。

2014-03-25 20:24:52

我對它很熟悉..但爲什麼你不會在處理器數量（p）上增加時間複雜度？ – Ohad

@Shiran網絡的每一層都可以與獨佔內存操作並行執行。總的工作是O（p log p），但時間只有O（log p）。 –

所以在模擬..我們只比較時間而不是工作？ – Ohad

回答