モチベーション

代表的な計算量にも色々あることを最近学んだ。

アルゴリズムを思いついたとき、その計算量がいくつなのかというのを瞬時に判断できるようにするために、各計算量のアルゴリズム例を自分の言葉でメモしておく。

計算量と具体例

$O(n)$

リストの各要素を順に見ていくようなとき。個数に比例して計算量が増える。

例）線形探索、リストでfor文まわす

$O(n^{2})$

2つのリストの全組み合わせを見ていくようなとき。

例）2重のfor

$O(n^{3})$

3つのリストの全組み合わせを見ていくようなとき。

例）3重のfor

$O(\log n)$

nがx倍されると計算量が1回増えるようなとき。

例）二分探索、X進法展開

$O(n\log n)$

nがx倍されると計算量が1回*x回になるようなとき。二分探索×線形探索のようなとき。

例）マージソート、分割統治法において分割された1つ1つ部分の計算量が $O(n)$ のとき

$O(\sqrt{n})$

そのままだけど、計算量が $O(\sqrt{n})$ のとき。例えばn=9で3回、n=16で4回のとき。

定数倍は無視だから、例えばn=9で6回、n=16で8回というようなアルゴリズムが出てきても同様に $O(\sqrt{n})$ なんだな。

例）素数判定

$O(n2^{n})$

$2^{n}$ 個数あるパターンを全て書き出して、そのパターンそれぞれに $n$ 回の処理をするようなとき。

例）部分和問題（ $2^{n}$ 個のパターンのリストを書き出したあと、求めている値になるか、全ての要素を足し合わせてるために $n$ 回の処理をする

$O(nn!)$

$n!$ 個数あるパターンを全て書き出して、そのパターンそれぞれに $n$ 回の処理をするようなとき。

例）巡回セールスマン問題（ $n!$ 個の道順のパターンを書き出したあと、所要時間を合計するために全てを足し合わせないといけない。）

サンダーボルト

相手モンスターを全て破壊する。