読者です 読者をやめる 読者になる 読者になる

並列化における効率化の目安は(n/log n)倍。たぶん。

分散化の場合のイメージと大分違うような気がするけど、直感レベルでの話しかしてないからよくわからない。
まあなんで僕が(n/log n)倍かというと、実際並列アルゴリズムが大体そんな感じっぽいから。

  • 畳みこみ(最大値や総和)の計算
    • O(n) → O(log n)
  • ソート
    • O(n log n) → O(log^2 n)