PowerPoint プレゼンテーション

基本情報技術概論 (第５回)
アルゴリズムとデータ構造
埼玉大学理工学研究科
堀山貴史
1
前回の復習
（ソフトウェアの基礎）

データ構造 … データをどのように記憶するか

基本的なデータ構造
 配列 (array)
A [1]
A [2]
A [3]
30
50
20
…
・データを順番に並べる
・添え字でアクセスする

リスト (list)
30
50
20
・となりの要素の位置を
ポインタとして持つ
2
前回の復習

その他のデータ構造
 スタック (stack)
30
50
20
・ L I FO
( Last-In First-Out )


待ち行列 (queue，キュー)
30
50
20
3
・ F I FO
( First-In First-Out )
木 (tree) 来週
3
練習：

A, B, C, D の順に到着するデータに対して、
１つのスタックだけを用いて出力可能なデータ列はどれか
ア.
イ.
ウ.
エ.
ウ
スタック
(H16年度春)
A, D, B, C
B, D, A, C
C, B, D, A
D, C, A, B
B
A
A
B
A
C
C
B
A
D
A
B
A
D
A
A
4
アルゴリズム

アルゴリズム
 問題を解決するための、有限ステップからなる手順
 自然言語や、流れ図（フローチャート）で示す
1.
2.
3.
4.
5.
6.
生協に行く
棚のチョコレートを手に持つ
レジに行く
財布から代金を払う
お釣りがあれば、受け取る
チョコレートを食べる
開始
1→i
i >n
Yes
No
A(i) = K
Yes
No
i+1→i
探索成功
の処理
探索失敗
の処理
終了
5
流れ図（フローチャート）

制御の流れを図で表したもの
基本的な記号
開始や終了
繰り返しの開始と終了
（ループ名、終了条件を
記述）
処理
参考：その他の記号
処理の流れ
条件に応じて、
次の処理を変える
（分岐条件を記述）
データの入出力
書類を印刷
ディスプレイに表示
6
アルゴリズム： ________________
線形探索 (linear search)

配列を先頭から順番に探索する

探索キーと同じキーが
配列の中に見つかれば
探索成功

A [1]
30
A [2]
50
A [3]
20
A [4]
70
A [5]
10
…
最後まで行っても
見つからなければ
探索失敗
探索キー
（探索データ）
70
7
アルゴリズム：

線形探索
(linear search)
配列を先頭から順番に探索する
開始
1→i
n：配列の要素数
K：探索キー
Yes
A(i) = K
No
i+1→i
Yes
i>n
No
探索失敗
の処理
100
K
70
i
A [1]
30
A [2]
50
A [3]
20
A [4]
70
A [5]
10
…
終了
探索成功
の処理
n
8
アルゴリズムの性能評価

計算量（時間計算量）
 大きさ n の入力に対して、
最悪の場合に必要な計算時間
例）線形探索
A[1] の探索は簡単だから
アルゴリズムの
計算時間は一瞬？
最悪の場合、
n 個全部
調べてね
A [1]
30
A [2]
50
A [3]
20
A [4]
70
A [5]
10
…
9
アルゴリズムの性能評価

計算量（時間計算量）
 大きさ n の入力に対して、
最悪の場合に必要な計算時間
 n に対する大まかな振舞いを見たいので
O （オーダ）表記をして、定数倍は無視する
例）線形探索
・最悪の場合、n 個全部調べる
・１個調べるには、３つの処理
計算時間 = 3 n … O(n)
10
アルゴリズム： ________________
２分探索 (binary search)

キーがソートされた配列に対し、高速に探索できる
A[ ]
1 2
1 2
3 4 5 6 7 8 9 10 11 12 13 14 15
5 10 35 50 70 100 110 150 190 191 200 300 400
探索キー
70

探索キーと配列中央のキーを比較
同じなら
… 探索成功
探索キー＜中央のキー … 前半分を探せばよい
探索キー＞中央のキー … 後半分を探せばよい
11
アルゴリズム：
２分探索
開始
1→L
n→H
M-1→H
(binary search)
n：配列の要素数 n
15
K：探索キー
L + H → M （小数点以下
2
切り捨て）
K
L
M
＞
H
No
A [1]
A [2]
A [3]
A [4]
A [5]
A [6]
A [7]
A(M) = K ＝
＜
探索成功
M+1→L
の処理
終了
1
2
5
10
35
50
70
…
L>H
Yes
探索失敗
の処理
70
12
アルゴリズム：

２分探索
(binary search)
計算量
A[ ]
1 2
1 2
3 4 5 6 7 8 9 10 11 12 13 14 15
5 10 35 50 70 100 110 150 190 191 200 300 400
探索キー
70

１回調べるごとに、探索範囲は半分になる
 最悪でも、log 2 n + 1 回調べれば良い

計算量は O( log n )
13
補足説明：
1
2
4
8
16
32
64
…
…
n回
2n
2倍
2倍
2倍
2倍
2倍
2倍
2倍
2倍
ｌｏｇ 2 ｎ
0
1
2
3
4
5
6
回
回
回
回
回
回
回
1
2
4
8
16
32
64
…
回
回
回
回
回
回
回
と
…
0
1
2
3
4
5
6
ｎ
２
log 2 n 回
n
2倍
2倍
2倍
2倍
2倍
2倍
2倍
2倍
14
アルゴリズムの性能評価

(比較)
計算量（時間計算量）
 O （オーダ）表記をする
O(1) < O( log n ) < O( n ) < O( n log n ) < O( n2 ) < …
例)
線形探索 O( n )
２分探索 O( log n )
50
40 n2
n log n
n
30
20
10
0
log n
10
20
30
40
n
50 15
アルゴリズム： ________________
バブルソート (隣接交換法)

隣り合うデータを見比べて、大小関係が逆なら交換
小大
小
が
バ
ラ
大バ
ラ
20
30
5
10
1
20
30
5
見比べて 1
交換
10
1
20
30
5
10
1
20
5
30
10
20
30
1
5
10
1 確定
20
バ
30
ラ
バ
5
ラ
10
20
1
30
5
10
1
5 確定
20
バ
ラ
30
バ
10
ラ
…
16
アルゴリズム：

n個
バブルソート
(隣接交換法)
計算量
1
20
30
5
10
確定
1
5
20
30
10
1
確定 5
10
20
30
１個目を確定させるのに２個目
比較が n – 1 回
n–2回
確定
…
1
5
10
20
30
３個目
… n - 1 個目
n–3回 … 1回
全部で O( n2 )
17
練習：

ソート
配列 A[ i ] ( i = 1, 2, ..., n ) を、次のアルゴリズムにより
整列（ソート）する。行 2 ～ 3 の処理が初めて終了した時、
必ず実現されている配列の状態はどれか。 (H19年度春)
1. i を 1 から n – 1 まで 1 ずつ増やしながら
行 2 ～ 3 を繰り返す
2. j を n から i + 1 まで 1 ずつ減らしながら
行 3 を繰り返す
3. A[ j ] < A[ j – 1 ] ならば、A[ j ] と A[ j – 1 ] を交換する
ア. A[ 1 ] が最小値になる
ウ. A[ n ] が最小値になる
イ. A[ 1 ] が最大値になる
エ. A[ n ] が最大値になる
18
アルゴリズム：

マージソート
ソートされた２つの列
→ １つにマージ（併合）するのは簡単
（各列の先頭を見比べながら、小さい方を取っていく）
5 20 25 50

(併合ソート）
1 10 30 40
１回のマージの実行時間は、要素数に比例
19
アルゴリズム：
マージソート
(併合ソート）
5 25 50 20 30 40 10 1
30 40 10 1
5 25 50 20
5 25
5
25
5 25
50 20
50
20
20 50
30 40
30
40
30 40
分割
10 1
10
1
1 10
マージ
log n 段
1 段に O( n ) 時間 → 全部で O( n log n ) 時間
21
練習：

スタック
A, B, C, D の順に到着するデータに対して、
１つのスタックだけを用いて出力可能なデータ列はどれか
(H16年度春)
ア. A, D, B, C
A
A
B
D
C
B
C
B
D
C
B
22
練習：

スタック
A, B, C, D の順に到着するデータに対して、
１つのスタックだけを用いて出力可能なデータ列はどれか
イ.
(H16年度春)
B, D, A, C
B
B
A
A
D
C
A
A
C
A
D
C
A
23
練習：

スタック
A, B, C, D の順に到着するデータに対して、
１つのスタックだけを用いて出力可能なデータ列はどれか
(H16年度春)
エ. D, C, A, B
C
B
A
B
A
A
D
C
B
A
D
C
B
A
C
B
A
24
25
アルゴリズム：

番兵付きの線形探索
ループの中の比較回数を減らす
開始
1→i
K → A(n+1)
Yes
A(i) = K
No
i+1→i
n：配列の要素数
K：探索キー
i>n
No
Yes
探索成功
の処理
100
K
70
i
A [1]
30
A [2]
50
A [3]
20
A [4]
70
A [5]
10
…
終了
探索失敗
の処理
n
26
アルゴリズム：

線形探索
(linear search)
配列を先頭から順番に探索する
開始
n：配列の要素数
K：探索キー
1→i
i>n
No
n
100
K
70
i
Yes
Yes
A(i) = K
No
i+1→i
探索成功
の処理
30
A [2]
50
A [3]
20
A [4]
70
A [5]
10
…
終了
探索失敗
の処理
A [1]
27
28
29
この教材のご利用について




この文面は、TOKYO
TECH OCW の利用
条件を参考にしました
この教材は、以下に示す利用条件の下で、著作権者にわざわざ許諾を
求めることなく、無償で自由にご利用いただけます。講義、自主学習は
もちろん、翻訳、改変、再配布等を含めて自由にご利用ください。
非商業利用に限定

この教材は、翻訳や改変等を加えたものも含めて、著作権者の許
諾を受けずに商業目的で利用することは、許可されていません。
著作権の帰属

この教材および教材中の図の著作権は、次ページ以降に示す著
作者に帰属します。この教材、または翻訳や改変等を加えたもの
を公開される場合には、「本教材 (or 本資料) は
http://www.al.ics. saitama-u.ac.jp/horiyama/OCW/ の教材です
(or 教材を改変したものです」との旨の著作権表示を明確に実施
してください。なお、この教材に改変等を加えたものの著作権は、
次ページ以降に示す著作者および改変等を加えた方に帰属しま
す。
同一条件での頒布・再頒布

この教材、または翻訳や改変等を加えたものを頒布・再頒布する
場合には、頒布・再頒布の形態を問わず、このページの利用条件30
この教材のご利用について

配布場所

http://www.al.ics.saitama-u.ac.jp/horiyama/OCW/

この powerpoint ファイルの著作者

堀山貴史 2007-2009 [email protected]

改変等を加えられた場合は、お名前等を追加してください
図の著作者

p. 4, 7, 9, 10, 11, 13, 18, 22 ～ 24
 クリップアート : Microsoft Office Online / クリップアート

その他
 堀山貴史

31

Download Report