データ構造とアルゴリズム | ②Big O 記法

こんにちは、現役理系大学生のShogoです！

第２回の内容は、「Big O 記法」です。

そもそも、Big O 記法は様々な呼ばれ方があります。

・Big O 記法
・Big O notation
・O 記法
・オーダー記法

『どこかで聞いたことがある気がするけど、いまいちわからない』という方におすすめの内容となっています！

あやふやだったBig O 記法を今回の講座で解決していきましょう！

2-1 Big O 記法とは

Big O 記法は、計算量を近似的に評価することを目的とした記法です。

ここでいう計算量には、時間計算量と空間計算量があります。計算量については、以前の記事で紹介しているのでそちらをご覧ください。

近似的とは、近いものを同じものとみなすということです。

例えば、円周率は3.14という値を使いますが、これも近似された値です。実際は、3.14159265...と限りなく続きます。しかし、3.14よりも小さい値を含まなくても、計算にあまり影響がないため、通常は省いて用いられています。

Big O 記法も同じようなことがいえます。

例えば、y = x のグラフとy = x + 5のグラフを次に示します。

（https://www.desmos.com/calculator?lang=ja）にて作成

あきらかに違いがわかると思います。では、これをより大きなスケールで見てみましょう。

重なっていて、ほとんど同じグラフに見えると思います。

したがって、スケールが非常に大きい場合、y = x のグラフとy = x + 5のグラフは近似できます。つまり、この2つの関数は近似できるので、どちらも同じBig O 記法で書くことができます。

もしこれをBig O 記法で書くとするならば、y = x + 5の切片を無視して、O(x)と書くことができます。

これはかんたんな例なので、続いてはBig O 記法のルールについて詳しく見ていきましょう。

2-2 Big O 記法のルール

Big O 記法は、関数の振る舞いを以下のルールに従って表記します。

1. 一番大きい項以外は無視する
2. 係数を取る
3. 結果をOの( )に入れる

例えば、

という関数を近似的に評価したいとき、1のルールに従うと、「2n」が無視されることがわかります。つまり、

となります。そして、この係数「4」を取るので、

となります。つまり、Big O 記法で書くと、

となります。

では、「2nlogn」ではどうでしょう。「2」をとって「nlogn」、つまり、O(nlogn)となるはずです。

2-3 Big O 記法による計算量の評価

出典：https://www.bigocheatsheet.com/

上図は、横軸が問題のサイズ、縦軸が計算量です。Big O 記法でグラフが何本か描かれています。

Big O 記法において、良い評価を得られるのが、問題のサイズが増えても、計算量が増えないものです。

例えば、1から10までの数字が書かれたカードがランダムに並べられています。これを1, 2, 3, ... , 10と並び替えたいとします。どのようにすれば最も速く並び替えられるでしょうか。

このときそれぞれの文は次のように置き換えられます。

1から10までの数字 → 問題のサイズ
並び替えるときの手数 → 計算量
並び替え方 → O(n)やO(nlogn)などのBig O 記法

例えば、並び替え方として上図で、O(n log n)を選んだとします。果たしてこれが並び替え方として最善でしょうか？

答えはNOです。この場合ではO(n)のほうがよりよい評価を得られます。なぜなら、O(n log n)に比べて、問題のサイズが増えても、計算量が増えないからです。

よく使われるBig O 記法の性能は、一般的に次のように示されています。

左に行くほど問題のサイズに対する計算量が減るので、性能がよくなります。

逆に、右に行くほど計算量が増えるので、性能が悪くなります。

2-4 Big O 記法をコードで解説

では、Big O 記法をコードで書くとどうなるのか。ここからは、pythonを用いたコードで解説していきます。ここでは関数のことをステップと呼ぶことにします。

✅反復

def func1(n):
   for i in range(n): # n回実行
       print(i)

func1(3) # このときn = 3なので3回実行

# 0
# 1
# 2

このときforループでn回実行しているだけなので、合計ステップは「n」。したがって、Big O 記法のルールに従うと、O(n)ということがわかります。

✅反復（n × n）

def func2(n):
   for i in range(n): # n回実行
       for j in range(n): # n回実行 
           print([i, j])

func2(3) # このときn = 3なのでn×nの9回実行

# [0, 0]
# [0, 1]
# [0, 2]
# [1, 0]
# [1, 1]
# [1, 2]
# [2, 0]
# [2, 1]
# [2, 2]

このときforループをn×n回実行しているので、合計ステップは「n×n」。したがって、Big O 記法のルールに従うと、O(n^2)=O(n×n)ということがわかります。

✅分岐

def func3(n):
   if n > 3:
       for i in range(n):  # n回実行
           print(i)
   else:
       print(n) # 1回実行

func3(2) # このときelseにいくので、1回実行 
# 2

func3(4) # このとき4 > 3で、n = 4なので4回実行
# 0
# 1
# 2
# 3

if文の場合、n回実行と1回実行に分かれているので、ステップが定まらないと思われます。

しかしこの場合は、実行回数、つまり、計算量の大きい方に分岐すると考えるので、n回実行。Big O 記法に基づくと、O(n)ということがわかります。

✅反復（n = n/2）

def func4(n):
   if n <= 1:
       return
   else: # logn回実行
       print(n)
       func4(n/2)

func4(32) # このときn = 32なのでlog32で5回実行
# 32
# 16.0
# 8.0
# 4.0
# 2.0

このコードは少しわかりにくいかもしれません。結果論ですが、説明していきます。

n = 1のときを考えると次のようになります。

　n = 1でfunc4(1)となる
→nの値がif n <= 1:に引っかかる
→returnで返され、func4(1)に
→else文のprintは実行されない
→数値は出力されない（故に0回実行）

次に、n = 2の時を考えます。

　n = 2でfunc4(2)となる
→このときのnは1よりも大きいので、else文へ飛ぶ
→printで「2」が出力（1回実行）され、func4(n/2)によって、値が半分に
→n = 1となり、func4(1)が実行
(→n = 1と同様)

n = 1のときは0回実行なので、出力は「2」で1回実行です。

n = 3を飛ばして、さらに、n = 4の時を考えます。

　n = 4でfunc4(4)となる
→このときのnは1よりも大きいので、else文へ飛ぶ
→printで「4」が出力（1回実行）され、func4(n/2)によって、値が半分に
→n = 2となり、func(2)が実行
(→n = 2と同様)

n = 2のときは1回実行なので、出力は「4」と「2」で2回実行です。

このようにn = 2で1回実行、n = 4で2回実行と考えると次のように考えられます。

このときkが実行回数です。この式は次のように変形できます。

よって、実行回数kがlognだということがわかります。

つまり、合計ステップはlogn、Big O 記法に基づくと、O(nlogn)ということがわかります。

まとめ

いかがだったでしょうか。

今回は、「O記法」についてお話しました。

O記法は、アルゴリズムを語る上では、必須の単元になってきますので、今回の講座でしっかりと覚えておくようにしてください！

質問や訂正があれば、遠慮なくこの記事にコメント、もしくは、TwitterにDMをしてください！(@shogo_python)

今回の記事が"いいね！"と思ってくれた方は、スキとフォローをよろしくおねがいします！

では、またの機会にお会いしましょう！

データ構造とアルゴリズム 入門講座 一覧はこちらから

データ構造とアルゴリズム | 入門講座｜Shogo｜note