PowerPoint プレゼンテーション

基本情報技術概論 I 演習 (第４回)
アルゴリズムとデータ構造
埼玉大学理工学研究科
堀山貴史
1
前回の復習：
アルゴリズム
アルゴリズム
 問題を解決するための、有限ステップからなる手順
 自然言語や、流れ図（フローチャート）で示す

重要・問題を解く鍵になるアイデアを把握
・アイデアを実現する手順を考える
1.
2.
3.
4.
5.
6.
生協に行く
棚のチョコレートを手に持つ
レジに行く
財布から代金を払う
お釣りがあれば、受け取る
チョコレートを食べる
開始
1→i
i >n
Yes
No
A(i) = K
Yes
No
i+1→i
探索成功
の処理
探索失敗
の処理
2
アルゴリズム： ________________
線形探索 (linear search)

配列を先頭から順番に探索する

探索キーと同じキーが
配列の中に見つかれば
探索成功

A [1]
30
A [2]
50
A [3]
20
A [4]
70
A [5]
10
…
最後まで行っても
見つからなければ
探索失敗
探索キー
（探索データ）
70
3
アルゴリズム：

線形探索
(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
4
アルゴリズム：

番兵付きの線形探索
ループの中の比較回数を減らす
開始
1→i
K → A(n+1)
Yes
A(i) = K
No
i+1→i
n：配列の要素数
K：探索キー
i>n
No
Yes
探索成功
の処理
100
K
90
i
A [1]
30
A [2]
50
A [3]
20
A [4]
70
A [5]
10
…
終了
探索失敗
の処理
n
5
アルゴリズムの性能評価

計算量（時間計算量）
 大きさ n の入力に対して、
最悪の場合に必要な計算時間
例）線形探索
A[1] の探索は簡単だから
アルゴリズムの
計算時間は一瞬？
最悪の場合、
n 個全部
調べてね
A [1]
30
A [2]
50
A [3]
20
A [4]
70
A [5]
10
…
6
アルゴリズムの性能評価

線形探索の
比較回数
最大 n
平均 n / 2
計算量（時間計算量）
 大きさ n の入力に対して、
最悪の場合に必要な計算時間
 n に対する大まかな振舞いを見たいので
O （オーダ）表記をして、定数倍は無視する
例）線形探索
・最悪の場合、n 個全部調べる
計算時間 … O(n)
成功
失敗
7
アルゴリズム： ________________
２分探索 (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

探索キーと配列中央のキーを比較
同じなら
… 探索成功
探索キー＜中央のキー … 前半分を探せばよい
探索キー＞中央のキー … 後半分を探せばよい
8
アルゴリズム：
２分探索
開始
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
9
アルゴリズム：

２分探索
計算量
A[ ]
1 2
1 2
２分探索の
比較回数
(binary search)
最大 log 2 n + 1
平均 log 2 n
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 )
10
補足説明：
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倍
11
アルゴリズムの性能評価

(比較)
計算量（時間計算量）
Q：図の線を
どう分類する？
50
40
30
20
10
0
10
20
30
40
n
50
12
アルゴリズムの性能評価

(比較)
計算量（時間計算量）
 O （オーダ）表記をする
O(1) < O( log n ) < O( n ) < O( n log n ) < O( n2 ) < …
50
例)
線形探索 O( n )
２分探索 O( log n )
40 n2
n2/2
n
30
20
n/2
10
log n
0
10
20
30
40
n
50
13
14
15
この教材のご利用について




この文面は、TOKYO
TECH OCW の利用
条件を参考にしました
この教材は、以下に示す利用条件の下で、著作権者にわざわざ許諾を
求めることなく、無償で自由にご利用いただけます。講義、自主学習は
もちろん、翻訳、改変、再配布等を含めて自由にご利用ください。
非商業利用に限定

この教材は、翻訳や改変等を加えたものも含めて、著作権者の許
諾を受けずに商業目的で利用することは、許可されていません。
著作権の帰属

この教材および教材中の図の著作権は、次ページ以降に示す著
作者に帰属します。この教材、または翻訳や改変等を加えたもの
を公開される場合には、「本教材 (or 本資料) は
http://www.al.ics. saitama-u.ac.jp/horiyama/OCW/ の教材です
(or 教材を改変したものです」との旨の著作権表示を明確に実施
してください。なお、この教材に改変等を加えたものの著作権は、
次ページ以降に示す著作者および改変等を加えた方に帰属しま
す。
同一条件での頒布・再頒布

この教材、または翻訳や改変等を加えたものを頒布・再頒布する
場合には、頒布・再頒布の形態を問わず、このページの利用条件16
この教材のご利用について

配布場所

http://www.al.ics.saitama-u.ac.jp/horiyama/OCW/

この powerpoint ファイルの著作者

堀山貴史 2007-2011 [email protected]

改変等を加えられた場合は、お名前等を追加してください
図の著作者

p. 3, 6, 8, 10
 クリップアート : Microsoft Office Online / クリップアート

その他
 堀山貴史

17

Download Report