Posted at

計算量オーダーのグラフ作った


はじめに

計算量オーダーの大きさの違いがわからなかったので、グラフを作ってみました。

$O(\log{n}) O(\sqrt{n}) O(n) O(n\log{n}) O(n\sqrt{n}) O(n^2) O(n^3) O(n^4) O(2^\frac{n}{2}) O(2^n) O(n!)$

上のの11個についてグラフにしてあります。

※計算量の小さい順に並べてあります。


全部含めたグラフ

横軸に$n$を取り、縦軸に$O(k)$を取っています。

横軸は続く3つのグラフで1メモリが10になっています。

$O(n\sqrt{n})$より大きくなるものは密集しすぎてわからないので、のグラフまで見送ります。

time_complexity1.jpg

圧倒的$O(\log{n})$の強さ。$O(\sqrt{n})$もいい戦いですね。

$O(n\log{n})$がいまいちピンと来なかったのですが、これを見ると$O(n)$より少し計算量が大きくなっている程度だということがわかります。


続き

縦軸のみ100倍くらい縮小して見てみます。

time_complexity2.jpg

$O(n\sqrt{n})$と$O(n^2)$が見えてきました。

この2つは計算量的にもまあまあ使えるゾーンですが、その他のものは天に向かって伸びていっております。

おそろしや。


続き

更に縦軸を$10^4$倍くらい縮小しました。

このグラフの天井は$10^8$となっているので、これを超えると厳しくなってくる計算量です。

time_complexity4.jpg

横軸が1メモリ10になっているのですが、$O(n^3)$以外は $n=100$ で力尽きてしまいます。

一方、$O(n^3)$を見ると、このグラフ上ではものすごく計算量が少ないように見えますが、$n$が増えるとぐんぐん成長していきます。

これらの計算量のアルゴリズムを使うときは、$n$と相談しながら使うのが良いのではないでしょうか。


教訓


  • アルゴリズムを考えるときは$n$と相談しよう

  • 計算量を考えよう


参考