pascalの日記: SuperCon2005(2).
日記 by
pascal
今回は久しぶりに時間を競う問題なのかな?
ものすごく単純な実装だとO(n^3)になるので、速い人(通称)と地下室でしばらくうんうんうなってました。
オーダはO(nlogn)まで落ちたらうれしいなとは思っていたのだけれどもまだ思い浮かばず(そもそも可能なのかしら)、速い人が見つけた中で一番スマートなものを実装してみました。
時間はマシンによってだいぶ異なるので参考程度ですが、PentiumM 1.3GHzのマシンで
単純な実装:45sec(どんな場合でもほぼ同じ)
明らかな最適化:11sec(最悪の場合)
くらいです。そのほかにもちょこちょこと最適化をかけられるところはあるのですが、まずは全体をスムーズにしてからかな。明らかな最適化の部分もまだいじりきってないところがあるので、どうなるかなぁ。
いじれば数秒にはなると思うけれど、正直当初目指していた1秒以内というのはこのままでは難しげ。
[追記]
最悪の場合、を考えにくくなる最適化を一行追加したら4秒になった。
SuperCon2005(2). More ログイン