アルゴリズムとデータ構造

(1)

2017/04/18 アルゴリズムとデータ構造 1

アルゴリズムとデータ構造

第４回基本的なデータ構造（ヒープ）

再帰的アルゴリズム

(2)

アルゴリズムとデータ構造２０１5 2015/11/04

2

• リストとは要素を０個以上１列に並べたもの

• リスト a ₀ ,a ₁ ,…,a _n-1 の実現法

1. 配列 (array)

2. 連結リスト (linked list)

3. 双方向連結リスト (doubly linked list)

a

₀

a

₁

・・・ a

_n-1

a

_n-1

null a

₁

a

₀

init ・・・

a

_n-1

null a

₁

a

₀

init null ・・・・・・ final

前回の復習 (1/ ３ )

• 配列は i 番目の要素への位置付けが容易、

（双方向）連結リストは挿入・削除が容易

i 番目の要素への位置付け挿入 or 削除

配列（双方向）連結リスト

O(1) O(n)

O(n) O(1)

(3)

3

リストの応用

• スタック

前回の復習 (2/ ３ )

要素の挿入、削除がいつも先頭からなされるリスト

LIFO(last-in-first-out)

a

₀

a

₁

a

₂

_PUSH(a

2

,S)

a

₀

a

₁

a

₂

a

₀

a

₁

a

₂

POP(S) TOP(S)

• 待ち行列（キュー）

要素の挿入は最後尾、削除は先頭からなされるリスト

FIFO(first-in-first-out)

a

₀

a

₁

ENQUEUE(a a

₂ ₂

,Q)

a

₀

a

₁

a

₂

TOP(Q)

a

₀

a

₁

a

₂

DEQUEUE(Q)

(4)

pr oc PUSH( x : el ement t ype; var S : st ack) ; begi n

i f S. t op : = 1 t hen wr i t el n( "ERROR! ") ; el se begi n

S. t op : = S. t op - 1;

S. el ement [ S. t op] : = x;

end end .

E

B A F

C D

10 9 8 7 6 5 4 3 2 1

el ement

5 t op

補足：配列によるスタックの実現

(5)

5

前回の復習 (3/3)

・・・

a

₀ ・・・

j

すべての操作の時間計算量は O(1)

キューの配列による実現

front

Q

TOP(Q)

ENQUEUE(a

_i+1

,Q)

a

_i ・・・

=

(j+i)%n

0

rear

n-1

DEQUEUE(Q)

a

₁

・・・

a

₀ ・・・

front

Q ^a

i ・・・

(j+i+1)%n

0

rear

n-1

a

₁

a

_i+1

・・・・・・

(j+1)%n front

a

_i ・・・

(j+i+1)%n

0

rear

n-1

a

₁

a

_i+1

j

バリエーション

Q

•rear

を最後尾の次のインデックスとする。

•rear

を保持せずに要素数

num

を保持し、

rear

は毎回

(front+num

－

1)%n

で計算しなおす。

「空（カラ）」か「空きなし」かの判断は？

・要素数

num

を保持する場合は

num=0

であれば空（カラ）、

num=n

であれば空きなし。

・要素が入っていない状態を表す特別な値

(

要素として現れない値

)

で配列を初期化し、

DEQUEUE

のときに取り出した位置を初期化する。

ENQUEUE

の時、追加しようとした

位置に要素が格納されていれば空きなし。

・要素の数を

n

－

1

までしか格納しない。

rear=(front-1)%n

であれば「空（カラ）」、

rear=(front-2)%n

の場合には「空きなし」と判断する。

(6)

A ₄ A ₅ A ₁ A ₂ A ₃

0 1 2 3 4 5

front rear

 配列で巡回リストを表わす．

 キューの長さ n が限定された場合

 先頭と末尾がつながって，輪になったリスト

 要素の位置を， n の剰余演算で決定.

補足：配列によるキューの実現

front から i 番目の要素 = Element[ (front + i) mod n ]

Element

ex. Elem[(head + 5) mod n] (head = 1 and n = 6)

= Elem[7 mod 6] = E[1]

(7)

A

F C B

E D

10 9 8 7 6 5 4 3 2 1

element

3 front

7 rear

配列によるキューの実現

(8)

優先度つき待ち行列

応用

(9)

要素間に全順序≦が定義されている集合

A.

(10)

Priority Queue の単純な実現方法

〜連結リスト（linked list）を用いる方法

整列しない場合

DELETEMIN( A )

O( n ) 時間

先頭から操作し，最小の要素をみつける．

INSERT( x, A )

O( 1 ) 時間

先頭に挿入するだけ．

あらかじめ整列した場合

DELETEMIN( A )

O( 1 ) 時間

先頭の要素を除くだけ

INSERT( x, A )

O( n ) 時間

先頭から操作し，順序を保って挿入する．

Header

a ₂ . . . an

a ₁

(11)

DELETEMIN と INSERT の両方の演算を

もっと効率良く実現できないか？

11

疑問

(12)

ヒープ (heap）

(13)

ヒープ（ heap ）

13

英語：「山積み」という意味．

(14)

14

優先度付き待ち行列（ヒープ , heap ）

集合

X

上の全順序（

total order,

線形順序（

linear order

））とは

X

上の要素間の２項関係

` ≦ ’

で、次の性質をもつものをいう。

(1) x ≦ x for all x ∈ X (

反射律

, reflexivity) (2) x ≦ y, y ≦ z ⇒ x ≦ z (

推移律

, transitivity)

(3) x ≦ y, y ≦ x ⇒ x=y (

反対称律

, anti-symmetry) (4) x ≦ y or y ≦ x for all x,y ∈ X (

比較可能性

, comparability)

全順序

` ≦ ’

が定義されている集合の要素を節点にもつ木で次のような条件を満たす２分木（各節点の子の数が高々２つの木）を考える。

ヒープ条件

任意の節点 u に対して

u の親の要素≦ u の要素が成り立つ。

2 5 8

7 10 11 9

10 11 12

* 初心者注意

(15)

15

ヒープの定義

ヒープ（ heap, 順位付きキュー（ priority queue ））とは

A[i] の親を A[ (i-1)/2 ] として定義される２分木がヒープ条件を満たす配列 A

i i+1 i+2

i-2 i-1

x

x x

y y = = y

2 5 8

7 10 11 9

10 11 12

( 例 ) ² ⁵ ⁸ ⁷ ^{10 11} ⁹ ^{10 11 12}

2 5 8

7 10 11 9

10 11 12

0 1 2 3 4 5 6 7 8 9

0

1 2

3 4 5 6

7 8 9

(16)

16

ヒープの定義

ヒープ（ heap, 順位付きキュー（ priority queue ））とは

A[i] の親を A[ (i-1)/2 ] として定義される２分木がヒープ条件を満たす配列 A

i i+1 i+2

i-2 i-1

x

x x

y y = = y

2 5 8

7 10 11 9

10 11 12

( 例 ) ² ⁵ ⁸ ⁷ ^{10 11} ⁹ ^{10 11 12}

2 5 8

7 10 11 9

10 11 12

0 1 2 3 4 5 6 7 8 9

0

1 2

3 4 5 6

7 8 9

(17)

17

ヒープの基本操作（最小要素の削除）

DELETEMIN(A) 最小（根にある）要素の削除 (n: 削除前の要素数 ) Step 1 A[0]←A[n-1], i←0

Step 2 2i+1 ≧ n-1 ならば停止。

そうでなければ j←argmin

_k∈{2i+1,2i+2},k<n

A[k] とする。

Step 3 A[i] ≦ A[j] ならば停止。

そうでなければ A[i] と A[j] の中身を入れ替え、 i← ｊとして Step 2 へ

実行例

12 5 8

7 10 11 9

10 11

i

Step 1 2

5 8

7 10 11 9

10 11 12

12 5 8

7 10 11 9

10 11

i

Step 2

j 5

12 8

7 10 11 9

10 11 Step 3 i

5 12 8

7 10 11 9

10 11 Step 2 i

j 5

7 8

12 10 11 9

10 11 Step 3 i

5 7 8

12 10 11 9

10 11 Step 2 i

j 5

7 8

10 10 11 9

12 11 Step 3 i

Step 2

停止

(18)

18

ヒープの基本操作（要素の追加）

INSERT(x,A) 要素の追加 (n: 追加前の要素数 ) Step 1 A[n]←x, i←n

Step 2 i=0 ならば停止。

そうでなければ j← (i-1)/2 とする。

Step 3 A[i] ≧ A[j] ならば停止。

そうでなければ A[i] と A[j] の中身を入れ替え、 i← ｊとして Step 2 へ

実行例

2 5 8

7 10 11 9

10 11 i

Step 1 2

5 8

7 10 11 9

10 11 12

2 5 8

7 10 11 9

10 11

Step 2

j

2 5 8

7 4 11 9

10 11

Step 3

2 5 8

7 11 9

10 11

Step 2 2 j

8 11 9

Step 3 2

8 11 9

Step 2 Step 3

停止

12 4 12 4 i 12 10

i

4 12 10 4 i

7 10 11

5 12 10 4 i

7 10 11

5 12 10

i j

(19)

19

ヒープの基本操作の時間計算量

DELETEMIN(A), INSERT(x,A) ともに、各 Step は定数時間で実行可能

Step 2 と Step 3 の間のループの回数のオーダーで実行可能

１回の繰り返し毎に DELETEMIN は i の位置が１つずつ深くなっていく

INSERT は i の位置が１つずつ浅くなっていく

最悪、木の高さの回数だけループする

要素数 n のヒープを２分木で表現した場合、木の高さは log

₂

n である。

DELETEMIN(A) と INSERT(x,A) の最悪時間計算量は O(log n)

証明してみよう！

* 初心者注意

(20)

(21)

整列問題の解法：ヒープソート

(22)

(23)

23

再帰呼出し

再帰呼出しとは

関数がその定義の中でそれ自身を呼び出すこと再帰的アルゴリズムとは

再帰呼出しを用いて記述されたアルゴリズム

(24)

24

再帰的アルゴリズムの例

最大公約数を求めるアルゴリズム（ユークリッドの互除法）

gcd(int m,int n) { int r=m%n;

if( r=0 ) return n;

else return gcd(n,r);

}

2 つの自然数 m,n(m ≧ n) の最大公約数は gcd(m,n)

gcd(int m,int n)

{ if( n=0 ) return m;

else return gcd(n,m%n);

}

実はもっと簡潔に以下のようにも書ける。

Ｅｕｃｌｉｄ（Ｅｕｋｌｅｉｄｅｓ）

ユークリッド（エウクレィデス）

（紀元前３００年ごろ）

(25)

25

再帰呼出しを使うことのメリット

• 記述が簡潔になる

• 理解しやすくなる

• アルゴリズムの正しさの証明がしやすくなる

• 計算量の解析が容易になる

(26)

26

再帰的アルゴリズムの作り方

1. 解くべき問題を、同じ問題でよりサイズの小さな問題を解くことに帰着させる。

（漸化式を立てる）

例） m と n(m ≧ n) の最大公約数は、 n と m%n の最大公約数と同じ。

gcd(m,n)=gcd(n,m%n) for n>0 2. 最小サイズの問題の解を示す。

例 ) m と n(m ≧ n) の最大公約数は、 m%n=0 のとき n

数学的帰納法で証明を書くつもりで！

(27)

27

何でも再帰呼出しにすれば良いというもでは・・・

gcd(int m,int n)

{ int a[2]={m,n}, i=1,j;

while(a[i]!=0) { j=(i+1)%2;

a[j]=a[j]%a[i];

} i=j;

return a[(i+1)%2];

} gcd(int m,int n)

{ if( n=0 ) return m;

else return gcd(n,m%n);

}

再帰呼出しを使わないと

×記述は少し複雑

○メモリ使用量は少ない

( スタック領域の使用量が少ない )

○計算時間も短い

( 関数呼出し、復帰処理がない ) 関数の最初または最後に

１回だけ再帰呼出しされる場合

ループを用いて比較的容易に

かける場合が多い

(28)

28

再帰呼出しの時間計算量

再帰的アルゴリズムの時間計算量＝

再帰呼出しの時間計算量＋再帰呼出し以外の時間計算量

プログラム

int factorial(int n) { if(n==1) return 1;

else return n*factorial(n-1);

} ( 例）

factrial(n) の実行時間を T(n) とおくと

再帰呼出し factrial(n-1) の時間計算量 =T(n-1) 再帰呼出し以外の時間計算量≦ C ( 定数 )

よって T(n) ≦ T(n-1) + C, T(1) ≦ C

したがって T(n) ≦ Cn=O(n)

(29)

29

ハノイの塔の演習問題を解いてみよう！

ハノイの塔は、フランスの数学者 E ・リュカ (Edouard Lucas) が 1883 年に考えたものである。リュカは、インドに次のような伝説があると説明している。

ブラフマーの塔

インドのガンジス河の畔のベナレス（ヴァラナシ）に世界の中心を表すという聖堂がある。そこには 3 本の大理石の柱（ダイヤモンドの針との説もあり）が立てられており、そのうちの 1 本には、当初 64 枚の黄金の円盤が大きい円盤から順に重ねられていたという。バラモン僧たちはそこで、一日中円盤を別の柱に移し替える作業を行っている。そして、全ての円盤の移し替えが終わったときに、この世は崩壊し終焉を迎えると言われている。

アルゴリズムとデータ 構造