『なっとく! アルゴリズム』メモその１ ビッグオー記法

『なっとく! アルゴリズム』を読んで並行して勉強したことをメモしておく。

なっとく! アルゴリズム

ビッグオー記法とは何か

アルゴリズムがどのくらい高速なのかをあらわすもの。英語の大文字Oを使用する。

どうやらこれはランダウの記号というらしい。

ランダウの記号（ランダウのきごう、英: Landau symbol）は、関数の極限における値の変化度合いに、おおよその評価を与えるための記法である。
ランダウの漸近記法 (asymptotic notation)、ランダウ記法 (Landau notation) あるいは主要な記号として O （オーもしくはオミクロン Ο。数字の0ではない）を用いることから（ランダウの）O-記法、ランダウのオミクロンなどともいう。
記号 O は「程度」の意味のオーダー（Order）から。 ランダウの記号 - Wikipedia

上記にも書いた通り、これでアルゴリズムがどれだけ高速であるのかをあらわすのだが、それを計算量という。
どれだけ高速なのかというのは、時間計算量という。

時間計算量には平均と最悪がそれぞれ存在する。
平均時間計算量：普通に処理したときの処理時間
最悪時間計算量：処理に一番時間がかかる場合に遭遇した時の処理時間

最悪時間計算量は単純に言うと、電話帳で「わ」から始まる人を調べるときに「あ」から順番に調べることと同義。
この場合、「あ」から「わ」まですべての人を見ていくことになるので途方もない時間がかかる。

ビッグオー記法の代表的な時間計算量

表記	意味	例	参照
	定数時間	ハッシュテーブルへのアクセス	定数時間 - Wikipedia
	対数	二分探索	対数 - Wikipedia
	線形関数	単純探索	一次関数 - Wikipedia
	線形対数	クイックソートのソートアルゴリズム
	多項式時間	選択ソートを使用した低速なアルゴリズム	多項式時間 - Wikipedia
	階乗関数	巡回セールスマン問題のような非常に低速なアルゴリズム

上の表で上に行くほど処理が速くて、下に行くほど処理が遅い。

どのくらい時間が違うか

pythonで1～10までのデータ個数でどのくらい違うのかを以下を参考にしつつあらわしてみる。

qiita.com

import numpy as np
import pandas as pd
import math

# 1～10の等差数列
input_data = np.arange(1,11,1)

o_1 = np.array([1,1,1,1,1,1,1,1,1,1])
o_log = np.log(input_data)
o_n = input_data
o_nlog = input_data * np.log(input_data)
o_n2 = input_data * input_data
o_n_fact = np.array([math.factorial(w - 1) for w in input_data] )

pd.DataFrame([o_1, o_log, o_n, o_nlog, o_n2, o_n_fact], index=["O(1)", "O(logn)", "O(n)", "O(nlogn)", "O(n2)" ,"O(n!)"])

上記実装の結果

は問題外として、定数のが一番早い。 KeyValue型のアクセスは高速であるということが分かる。*1

データ個数が少ない場合は処理時間にそんなに変化がないことは分かるが、大きくなればなるほどその差が如実にあらわれる。

はアルゴリズム上ハッシュテーブルへのアクセス程度にしか使えないので、ソート等のアルゴリズムを見たときにが一番早いと認識してよさそう。

そもそもってなんだろう

が速いってことは分かった。

だけど、そもそも「」って何だって話。

atarimae.biz
ここにも書いているが、「〇を何乗すると×になるか」ということをあらわす。これを対数という。

の場合、2を何乗したら8になるのかということ。

この時のが対数。 言い方的には「2を底とする8の対数」と言うらしい。

この場合、「2を底とする8の対数」は3となる。

で、上に戻って「log n」の話になるんだけど、これ代入できる数値ひとつしかないじゃないの？って思った。

「???を底とするのn対数」この???はどこに行ったのか。

自然対数とネイピア数

「???を底とするのn対数」この???を理解するためには自然対数を理解しなければならない。

自然対数とは、「ln（エルエヌ）」とも書き、「ネイピアの数eを底とする対数」のことです。
自然対数lnとは？底のeって何？定義や微分積分、常用対数変換公式も紹介 | Studyplus（スタディプラス）

ネイピア数（ネイピアすう、英: Napier's constant）は数学定数の一つであり、自然対数の底である。ネーピア数とも表記する。記号として通常は e が用いられる。その値は

e = 2.71828 18284 59045 23536 02874 71352 …
と続く超越数である。ネピアの定数、ネピア数とも呼ばれる。欧米ではオイラー数 (Euler's number) と呼ばれることもあるが、オイラーの定数 γ やオイラー数列とは異なる。オイラーにちなんで名づけられた物事の一覧#オイラー数（英語版）も参照。
ネイピア数 - Wikipedia

「」は「」のことであるよう。

「」は省略可能なので 上の書き方で書くならば「ネイピア数を底とするのn対数」ということになる。

*1:こんなことしなくてもわかることではあったが