gpt4 book ai didi

algorithm - 模拟理论 - 如何排序只有 log(p)?

转载 作者:塔克拉玛干 更新时间:2023-11-03 06:00:33 25 4
gpt4 key购买 nike

在模拟理论的证明中:模拟并发写入:“crcw 算法中的 p 处理器不能比 log(p)time 更快,然后是针对同一问题的最佳 erew 算法”

enter image description here

谁能解释一下为什么在模拟证明中只需要 log(p) 来按第一个分量而不是 O(plogp) 对数组进行排序?

最佳答案

排序是与日志深度并行完成的 sorting network . AKS 构造是银河算法的一个很好的例子。 Batcher's bitonic sorting network深度 log^2 n 在实践中更合理。

关于algorithm - 模拟理论 - 如何排序只有 log(p)?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22645112/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com