Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
Help us understand the problem. What is going on with this article?

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

はじめに

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

$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$と相談しよう
  • 計算量を考えよう

参考

kokorinosoba
はたらきたくない
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away