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

Programming Algorithm

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

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