PowerPoint プレゼンテーション

コンピュータ基礎演習
ー探索、整列ー
岩井儀雄
[email protected]
線形探索と二分探索

線形探索法(linear search)
データを最初から順番に探索する
例）{2, 4, 5, 8, 9, 11, 6, 7, 15, 20} から15を探す
最初の要素から始めて９回目→計算量O(n)


二分探索法(binary search)

データをあらかじめソートしておき，中央の要素から検
索する．
二分探索(binary search)

{2, 4, 5, 6, 7, 8, 9, 11, 15, 20} から15を探す
１回目
{2, 4, 5, 6, 7, 8, 9, 11, 15, 20}
二分探索(binary search)

{2, 4, 5, 6, 7, 8, 9, 11, 15, 20} から15を探す
２回目
{2, 4, 5, 6, 7, 8, 9, 11, 15, 20}
二分探索(binary search)

{2, 4, 5, 6, 7, 8, 9, 11, 15, 20} から15を探す
３回目
{2, 4, 5, 6, 7, 8, 9, 11, 15, 20}
探索回数
計算量
３回
log2(n)
O(log n)
整列(sort)

内部整列(internal sort)


主記憶上で行う整列
外部整列(external sort)

外部記憶装置（テープ等）上で行う
整列アルゴリズムの優劣→比較回数と交換回数の大小
安定な整列(stable sort)

同じ値を持つデータ間の順序関係が整
列の前後で保たれている
例）整列前： 7 9 5A 4 8 5B 2
整列後： 2 4 5A 5B 7 8 9 （安定）
整列後： 2 4 5B 5A 7 8 9 （不安定）
単純な整列（バブルソート）

配列の後ろから先頭に向かって走査し，もし隣り合う二つ
の要素の大小関係が逆であったら入れ替える
整列前 20 6 55 74 3 45 13 87 46 30
１回目
比較
単純な整列（バブルソート）

配列の後ろから先頭に向かって走査し，もし隣り合う二つ
の要素の大小関係が逆であったら入れ替える
１回目 20 6 55 74 3 45 13 87 30 46
入替
単純な整列（バブルソート）

配列の後ろから先頭に向かって走査し，もし隣り合う二つ
の要素の大小関係が逆であったら入れ替える
１回目 20 6 55 74 3 45 13 87 30 46
比較
単純な整列（バブルソート）

配列の後ろから先頭に向かって走査し，もし隣り合う二つ
の要素の大小関係が逆であったら入れ替える
１回目 20 6 55 74 3 45 13 30 87 46
入替
単純な整列（バブルソート）

配列の後ろから先頭に向かって走査し，もし隣り合う二つ
の要素の大小関係が逆であったら入れ替える
１回目 20 6 55 74 3 45 13 30 87 46
比較
単純な整列（バブルソート）

配列の後ろから先頭に向かって走査し，もし隣り合う二つ
の要素の大小関係が逆であったら入れ替える
１回目 20 6 55 74 3 45 13 30 87 46
比較
単純な整列（バブルソート）

配列の後ろから先頭に向かって走査し，もし隣り合う二つ
の要素の大小関係が逆であったら入れ替える
１回目 20 6 55 74 3 13 45 30 87 46
入替
単純な整列（バブルソート）

配列の後ろから先頭に向かって走査し，もし隣り合う二つ
の要素の大小関係が逆であったら入れ替える
１回目 20 6 55 74 3 13 45 30 87 46
比較
単純な整列（バブルソート）

配列の後ろから先頭に向かって走査し，もし隣り合う二つ
の要素の大小関係が逆であったら入れ替える
１回目 20
20
20
20
3
6 55 74 3 13
6 55
3 74 13
6
3 55 74 13
3
6 55 74 13
20 6 55 74 13
45
45
45
45
45
30
30
30
30
30
87
87
87
87
87
46
46
46
46
46
単純な整列（バブルソート）

配列の後ろから先頭に向かって走査し，もし隣り合う二つ
の要素の大小関係が逆であったら入れ替える
２回目 3 20 6 55 74 13 45 30 87 46
46 87
30 46
30 45
13 30
13 74
13 55
6 13
6 20
単純な整列（バブルソート）

配列の後ろから先頭に向かって走査し，もし隣り合う二つ
の要素の大小関係が逆であったら入れ替える
２回目
３回目
４回目
５回目
６回目
７回目
８回目
９回目
3
3
3
3
3
3
3
3
6
6
6
6
6
6
6
6
20
13
13
13
13
13
13
13
13
20
20
20
20
20
20
20
55
30
30
30
30
30
30
30
74
55
45
45
45
45
45
45
30
74
55
46
46
46
46
46
45
45
74
55
55
55
55
55
46
46
46
74
74
74
74
74
87
87
87
87
87
87
87
87
バブルソート（疑似コード）
for (i←0..n-1)
for (j←n-1..i)
if !(a[j-1] ≦ a[j])
swap(a[j-1],a[j])
右辺値の交換
整列アルゴリズムが満たす事後条件
 < j]  a[i]  a[ j]
i,j[i
計算量は O(n2)
バブルソート（Ｃ言語）
for (i←0..n-1)
for (j←n-1..i)
if !(a[j-1] ≦ a[j])
swap(a[j-1],a[j])
void bubble_sort(int a[],int n) {
int I,j,t;
for (int I=0; I<n-1; ++I)
for (int j=n-1; j>I; --j)
if (a[j-1] > a[j]) {
t = a[j]; a[j] = a[j-1]; a[j-1] = t;
}
swap(a[j-1],a[j])に相当する
}
単純な整列（選択ソート）

未整列部分から最小の要素を選び出し，それを未整
列部分の先頭と入れ替える
  a[1] 
a[0]
整列済
 a[i –1]  a[i] 
a[n –1]
未整列部分
未整列部分から最小値を取り出し
続けると下記の条件を満たす
整列アルゴリズムが満たす事後条件
 < j]  a[i]  a[ j]
i,j[i
選択ソート
整列前 20
１回目
6
55
入替
74
3
45
13
87
46
30
選択ソート
整列前 20
１回目 3
6
6
55
55
74
74
3
20
45
45
13
13
87
87
46
46
30
30
選択ソート
整列前 20
１回目 3
２回目 3
6
6
6
55 74
3 45 13 87 46 30
55 74 20 45 13 87 46 30
55 74 20 45 13 87 46 30
入替
選択ソート
整列前 20
１回目 3
２回目 3
３回目 3
４回目 3
５回目 3
６回目 3
７回目 3
８回目 3
９回目 3
6 55
6 55
6 55
6 13
6 13
6 13
6 13
6 13
6 13
6 13
74
74
74
74
20
20
20
20
20
20
3
20
20
20
74
30
30
30
30
30
45
45
45
45
45
45
45
45
45
45
13
13
13
55
55
55
55
46
46
46
87
87
87
87
87
87
87
87
55
55
46
46
46
46
46
46
46
55
87
74
30
30
30
30
30
74
74
74
74
87
選択ソート（疑似コード）
for (i←0..n-2)
lowest←argmin(a[j])
i<j<n
swap(a[i],a[lowest])
選択ソート（Ｃ言語）
void selection_sort(int a[],int n) {
int i,j,t,lowest,lowval;
for (i = 0; i<n-1; ++i) {
argminの計算部分
lowest = i; lowval = a[i];
for (j = i+1; j < n; ++j)
if (a[j] < lowval) {
lowval = a[j]; lowest = j;
}
t = a[I]; a[I] = a[lowest]; a[lowest] = t;
}
}
選択ソートの計算量


ループ n 回，argmin の計算量 O(n)
選択ソートの計算量は O(n2)
単純な整列（挿入ソート）

配列の一部分が整列済みの時に，残りの要素
を一つずつ整列済みの中に挿入する
整列前 20 6 55
１回目 6 20 55
２回目 6 20 55
３回目 6 20 55
４回目 3 6 20
５回目 3 6 20
６回目 3 6 13
７回目 3 6 13
８回目 3 6 13
９回目 3 6 13
74
74
74
74
55
45
20
20
20
20
3
3
3
3
74
55
45
45
45
30
45
45
45
45
45
74
55
55
46
45
13
13
13
13
13
13
74
74
55
46
87
87
87
87
87
87
87
87
74
55
46
46
46
46
46
46
46
46
87
74
30
30
30
30
30
30
30
30
30
87
挿入ソート（疑似コード）
for (i←0..n-1)
j←i
while (! (a[j-1] ≦ a[j]) )
swap( a[j-1], a[j] )
j←j-1
計算量：外側ループ O(n)
内側ループ O(n)
合計： O(n2)
コンピュータ基礎演習
ー計算量ー
岩井儀雄
[email protected]
計算量(complexity)

時間計算量(time complexity)


空間計算量(space complexity)



アルゴリズムがデータに対してどれくらい時間がかかるか
を示す
アルゴリズムがデータに対してどれくらい記憶領域を必要
とするかを示す
時間計算量と空間計算量はトレードオフの関係にあ
ることが多い
計算機にとって記憶資源は潤沢にあるので，通常時
間計算量の方が重きを置かれることが多い
オーダー記法Ｏ

計算量T(n)の上界値を評価するとき，
O(f(n))という記法を用い，オーダーf(n) と
読む．

c,n 0 c > 0, n  n 0  T(n)  cf (n)
ある正定数cとn0が存在して，n0以上のnに対して，
常に T(n) ≦cf(n) が成立するという意味
n0の役割は有限個の例外を許すことにある．
オーダー記法Ω

計算量の下界値のオーダーを表すには，
記法Ωを用いる．T(n)=Ω(f(n))とは，

cn T(n)  cf (n)
計算量とオーダ表記の関係
計算量の上界O
計算量
実際の計算量
有限個の
例外はOK
計算量の下界Ω
n0
n
オーダーの演算

T1 = O( f (n)), T2 = O(g(n))
T1 + T2 = O(max( f (n),g(n)))
T1  T2 = O( f (n) g(n))
例） T1 = O(n 2), T2 = O(n 3)
T1 + T2 = O(n 3)
T1  T2 = O(n 5)
最悪計算量と平均計算量


同じアルゴリズムでも入力するデータに応じ
て計算量が変化する．そこで，客観的に測定
し評価する必要がある．
最悪計算量 worst case complexity


全ての入力パターンに対して最大の計算量を要す
るものに基づいて定める
平均計算量 average complexity

全ての入力パターンとその入力の生起確率に基づ
いて計算量の平均を求める

Download Report