競プロを頑張るブログ

問題を解いてる時の思考なりをまとめていきます

計算量の見積もり方

競プロ競技プログラミング

こんにちは！

ひぽたふです。

競プロの考察時に、どのくらいの計算量になるんだろう？
って毎度悩まされますよね。

ループの数は見やすいところですが、ちょっと複雑になると書いてみないと計算量をイメージしにくかったりするのが厄介なところ。

アルゴリズム単位ではよく記事にまとめられてますよね。
二分探索が $O(log(n))$ だとか、ワーシャルフロイドは $O(V^{3})$ だとか。

じゃあそれらを使って実際どう最終的なオーダーを求めるの？
どのくらいなら間に合うの？
っていう話周りをまとめておこうかなって思いました！

全探索
DP
二分探索とか
通る回数
まとめ

全探索

間に合えば全探索したいって問題結構多いですよね。

そんな時に重要になってくるのが計算量！

全探索の問題は、 $O(2^{n})$ , $O(n!)$ って事が多いかなと思います。

とある数列の中から何個か選んで、特定の何かにしたい！って時は $O(2^{n})$ がベースになると思います。
問題の具体例としては、部分和問題だったり、ナップサック問題だったり。

f:id:hipotaf:20200609030154p:plain

bitをイメージして貰えるとわかりやすいのですが、 $2^{n}$ までの数値を使えば、全てのパターンを列挙できますよね？
例えば、 $n = 2$ なら、00, 01, 10, 11といった感じに。

さらに、例えば今の状態が 10111001 だったとして、その状態を計算するのにはどのくらいかかるかも見積もる必要があります。

部分和問題であれば、1が立っている場所の数値を全部足してみないと答えがわからないので、bitの数だけ追加で計算コストがかかります。つまり $O(n)$ が追加で必要になり、最終的に $O(n \cdot 2^{n})$ になります。

$O(n!)$ は順番も考慮する場合に出てきます。
組み合わせの話を覚えてると早いと思いますが、 $n$ 種類の中から1つ決めて、1個減った中からまた1つ決めて・・・繰り返していくと $n \cdot (n - 1) \cdot (n - 2)$ ...となるイメージがつくと思います。

オーダーがわかったら実際間に合うかも検討しなきゃならないですね。
だいたい10⁷くらいであれば間に合います。

$O(2^{n})$ から考えてみます。
2²⁵が10⁷よりちょっと多いくらいなので、この辺りが分かれ目になります。

ナップサックも $n = 25$ くらいだったら間に合いそうかな！って事ですね。

$O(n!)$ はかなり厳しいです。
10!が上限というところですね。

DP

全探索が計算量的に厳しかったらDPに移行しましょう。

DPの計算量はとてもわかりやすく見積もれます。

例えば、適当にdp(i, x)のように2変数あるDPを考えてみると、 $O(i * x)$ になります。

そうです、引数を全部掛け合わせれば見積もる事ができます。

これに分岐量を考慮してあげれば最終的な計算量になります。

ナップサックだと、目の前の宝石を取るか取らないかの2分岐なのでオーダーは変わらないですね。
グラフとかだと、今のノードから他全部のノードに分岐する可能性があったりして $O(i * x * ノード数)$ とかになってくるわけです。

この分岐にかかる計算量を工夫して減らしたり、引数が取りうる状態を減らしたりして計算量を10⁷くらいに収めるわけですね。

大枠のオーダー * コスト計算なりの内部オーダーという視点があると一気に計算量が求めやすくなると思います。

部分和問題なら $O(2^{n})$ が大枠、 $O(n)$ が内部。
DPなら $O(引数の総乗)$ が大枠、 $O(分岐)$ が内部。

ダイクストラで大枠を計算しつつ、各ノードで追加計算　　とか
二分探索で条件を変えつつ、ダイクストラでコスト計算　　とか

計算量から逆算して、大枠はこのくらい、なら内部はこのくらい
のように問題の分割もしやすくなるんじゃないかなって思います。

二分探索とか

単体で出てくる事が割と多い印象の二分探索。

突然組み合わせるとなると結構困る事があります。

そんな時に、計算量を考えてあげると登場してもらいやすいのかなって最近思っています。

二分探索のオーダーは $O(log(n))$ ですね。

この $n$ について、10⁸くらいなら $log(n)$ は20とちょっとくらいまで小さくなります。

DPなんかの計算量を考えてる時に、分岐に関する計算量が膨れた時なんかは影から二分探索が覗いているかもしれません。

関数に対しての二分探索とかは、 $O(log(n) * 関数のオーダー)$ になるので、関数の計算量は10⁶くらいまでいけそうだ。って感じで見積もれたりします。

通る回数

単純なループじゃないと計算量の見積もりの難易度が上がってくると思います。

そういう時、各ノードを何回踏むかをイメージすると見積もりやすいかと思います。

BFSを使ってグリッド上にある迷路の最短路を求めるときなんかは、同じ道を何回も通らないですよね？
そのイメージ通り、マス目の数を $n$ として $O(n)$ になります。

しゃくとり法も同じように考えて、配列の上を頭が1回・尻尾が1回通るだけなので、 $O(n)$ になるイメージがつくのではないでしょうか。

f:id:hipotaf:20200609030758p:plain

オーダーを忘れた時や、ちょっと入り組んだアルゴリズムのオーダーを考える時なんかは考えやすいんじゃないかなと思います。

まとめ

大枠のオーダー・内部計算のオーダーに分けて考える！
DPは引数の総乗で大枠のオーダーが出る！
$log(n)$ で10⁸だろうと20程度に小さくなる！
特定の場所を踏む回数を考えれば、未知のオーダーも怖くない！

それでは、またっ！！