20180525_4_complexity

(20140618)

アルゴリズムの評価（計算量）

計算量（complexity 直訳すると複雑性）

	時間計算量：処理の回数→実行時間
	領域計算量：作業用データの量→記憶容量

	問題（データ）のサイズｎの関数で表現する
		例．ｎの二乗
		　　log(n)

	最悪値（○）
	最良値
	平均値（○）

（例）バブルソート：ソーティングのアルゴリズムのひとつ

○時間計算量

問題のサイズをｎとして、
比較の回数を調べる。
交換の回数を調べる。

外側のループは(n-1)回だけ繰り返す。
内側のループは、
　　外側ループの１回目のとき、(n-1)回だけ繰り返し、
　　　　　　　　２　　〃　　、(n-2)　　　〃
　　　　　　　　：
　　　　　　　　：
　　　　　　　　n-1 　〃　　、１回だけ繰り返す。
したがって、比較の回数の合計は、
　　(n-1) + (n-2) + … + 2 + 1 = n(n-1)/2
ただし、
係数の1/2などは、計算機のクロックの違いなどにより、
無視することができ、
ｎの１次の項は２次の項に比べて小さいので無視できる。
結局、「ｎの二乗に比例する計算量である」といえる。
これを、
「Ｏ(nの二乗)」と書いて「オーダー、ｎの二乗」という。

クイックソートの平均の時間計算量は、O(n・log(n))。

バケットーソートの時間計算量は、o(n + m)。
（ここに、ｎはデータの個数、ｍはデータが取り得る値の場合の数。）

○各種のソートアルゴリズムの計算量の比較

データサイズ	バブル		クイック	バケット
	ｎ	ｎ・ｎ		ｎlogｎ		ｎ（＋ｍ）
	10	   100	
       100	 10000
      1024	約100万		  10240		   1024

○理論的にソーティングの時間計算量を見積もる。

ｎ個のデータの並びのとりうる場合の数はいくつか？
　　n(n-1)(n-2)…3・2・1 = n!
ｐ：あるデータの並びが実現する確率。
　　p = 1/(n!)

情報量Ｉの式
	 I = - log(p)
	   = log(n!)
	　≒ n・log(n)