パスワードを忘れた? アカウント作成
568725 journal

pascalの日記: SuperCon2005(2).

日記 by pascal

今回は久しぶりに時間を競う問題なのかな?
ものすごく単純な実装だとO(n^3)になるので、速い人(通称)と地下室でしばらくうんうんうなってました。

オーダはO(nlogn)まで落ちたらうれしいなとは思っていたのだけれどもまだ思い浮かばず(そもそも可能なのかしら)、速い人が見つけた中で一番スマートなものを実装してみました。

時間はマシンによってだいぶ異なるので参考程度ですが、PentiumM 1.3GHzのマシンで

    単純な実装:45sec(どんな場合でもほぼ同じ)
明らかな最適化:11sec(最悪の場合)

くらいです。そのほかにもちょこちょこと最適化をかけられるところはあるのですが、まずは全体をスムーズにしてからかな。明らかな最適化の部分もまだいじりきってないところがあるので、どうなるかなぁ。

いじれば数秒にはなると思うけれど、正直当初目指していた1秒以内というのはこのままでは難しげ。

[追記]
最悪の場合、を考えにくくなる最適化を一行追加したら4秒になった。

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
typodupeerror

Stableって古いって意味だっけ? -- Debian初級

読み込み中...