計算量のはなし - 赤い黒歴史を蓄積する

どうも華麗なるキャッツパーです。キャットアッパーです。 この記事はCompetitive Programming Advent Calendar Div2013, 12/7の記事です。 私は過去に、暇に任せてこのようなスライドを作ってしまいました。 有名アルゴリズムとそれの計算量について列挙するのが楽しすぎて作ってしまいました。後悔しております。 本記事では「計算量ってどうやって計算するの？」みたいな話を競プロの観点からします。 計算量とはなんぞやということについては上のスライドを読んでください。 計算量の種類 競技プログラミングで気にする計算量は2種類あります。最悪計算量と償却計算量です。 最悪計算量というのは、ある処理にどのような入力を与えても、それ以上に速い計算量になる、というもので、一種の上界です。競技プログラミングでは作問者が最悪計算量になるテストケースをかならず入れてきますから

[mooz]

平均計算量と償却計算量。アンサンブル平均と時間平均。ポテンシャル解析。

[UDONCHAN]

参考になる

[siuye]

O(10^8)とかの表現を見ただけで、ちょっと不安になる。オーダー記号、わかってないのか、わかりつつ、書いているのか。

[bayan]

むずかちい

[overlast]

"期待する計算量を当てはめてみてうまくいくか確認"