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

という気がしてきたので、文字列検索の有限オートマトン化をしてみた。…普通にこれでいいじゃん！有限オートマトンの生成にかかる時間およびメモリはn=キーサイズ,c=文字の種類とおいてO(cn)なので、そこで少し遅れをとるけど、検索が非常にシンプルで高速(…