ところでどなたか、シェルソートがO(?)なのかご存じの方はいらっしゃらないでしょうか。O(n(log n)2)という人もいるし、O(n1.25)という人もいるし.... http://blog.livedoor.jp/dankogai/archives/50962504.html シェルソートは、挿入ソートを行う間隔の取り…

ただしくは、検索対象のシーケンスの長さを m として、ナイーブな実装では最悪時間計算量は O(m log n)。Longest Common Prefix(LCP) を計算しておいて、さらに LCP を対象として Range Minimum Query(RMQ) の前準備をしておけば、O(m + log n)。 http://d.h…