#Pythonで学ぶアルゴリズム< アルゴリズムの評価 >

##はじめに
基本的なアルゴリズムをPythonで実装し，アルゴリズムの理解を深める．
その第8弾としてアルゴリズムの評価を扱う．今回は実装はしないが，アルゴリズムを学んでいく中で，どのようにアルゴリズムを評価するのかという基礎的なところをまとめる．

##プログラムはどのように評価するのか？
実装していくつかのデータで計測し1つ1つ試して評価する？

単純な発想でわかりやすいが，次のような問題が出てくる
・プログラム設計時には評価できない
・環境や言語に依存するかもしれない

だから…
**計算量(Computational Complexity)**という考えがある

##計算量(Computational Complexity)
計算量には時間計算量や空間計算量，ほかにも通信計算量や回路計算量など，様々なものがある．

プログラム上でよく評価の指標として使われるのが時間計算量と空間計算量である．
時間計算量：処理時間を指す
空間計算量：メモリなどの記憶容量をどれくらい必要とするのかを指す

例）
フィボナッチ数列を幾つか記憶した状態でプログラムすれば，時間計算量は減らせるが，事前に記憶するための空間計算量が大きくなる．

##擬似的処理時間
実際の処理時間$[s]$を測ると，実行環境にも影響し得るため，その1つの処理に対してかかる時間を定数とし，繰り返し数に比例するという形にして，これを計算量としてとらえて評価する．

例えば，次のようにfor文で50回まわし，1回ずつprint処理をすることを考える．

for i in range(50):
    print(i)

このとき，print1回の処理時間を$a$とすると，このプログラムの処理時間は$a\times50$と考えられる．これを50ではなく，任意数$n$回とすると，その処理時間は$a\times50$と考えることができる．

n = 100 # 任意数
for i in range(n):
    print(i)

これは，ある処理に対して，プログラム処理時間はデータ数$n$に比例しているといえる．
ほかにも例を挙げる．

n = 100 # 任意数
for i in range(n):
    for j in range(n):
        print(i)

この場合，処理時間は$a\times n \times n=a\times n^2$と考えられる．（$n^2$に比例）

n = 100 # 任意数
for i in range(n):
    for j in range(n):
        for k in range(n):
            print(i)

このようにfot文3つを入れ子状態にすると，処理時間は$a\times n \times n \times n=a\times n^3$と考えられる．（$n^3$に比例）

このようにある定数にデータ数$n$を掛け合わせて，処理時間がデータ数に対してどのように関係しているのかというのを処理時間と考えたものを擬似的処理時間とし，次に示すオーダー記法の考えになる．

##オーダー記法
$n$個のデータに対してどのくらいの割合で処理時間がかかるのかを$O$(~)の形で表したもの

##感想
今まで，時間[s]で処理時間を計測して，いくつかのアルゴリズムを評価していたが，今回のオーダー記法というものを知って，確かに，環境や言語に依存し得るものに対してはこのような共通の指標というものは大事だと思った．ただ，単純にあるアルゴリズムと他の方法の相対的な評価であるならば，実際にかかった時間で評価することもありなのかと感じるとともに，実際にそのようなことで評価している論文もあるからそうなのだろうと思う．ただ，アルゴリズム自体の絶対的評価（そのアルゴリズムは本当に優秀なのか）というのであれば，オーダー記法のほうが分かりやすく，信頼性があると思う．「for文を回しすぎるのはよくない」ということをpythonを学び始めたころに聞いたことがあったが，このことだったんだなと納得できた．

##参考文献
Pythonで始めるアルゴリズム入門　伝統的なアルゴリズムで学ぶ定石と計算量
　　　　　　　　　　　　　　　　　　　　　　　　増井敏克　著　　翔泳社