結論は正しいけど導く過程が何か間違っている。 最悪のケースの美しさここで、どんな場合に互除法が最も苦戦するかを考えてみましょう。余りで割ることを繰り返しているのですから、この余りがなるべく減らないような整数の対を用意すればいいことになります…

ところでどなたか、シェルソートが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…