基本情報技術概論（第５回） 埼玉大学 理工学研究科 堀山 貴史 2008/5/22 基本情報技術概論 (第５回) アルゴリズム と データ構造 埼玉大学 理工学研究科 堀山 貴史 2008/01/23

前回の復習 （ソフトウェアの基礎） データ構造 … データをどのように記憶するか 基本的なデータ構造 配列 (array) 前回の復習 （ソフトウェアの基礎） データ構造 … データをどのように記憶するか 基本的なデータ構造 配列 (array) リスト (list) 30 50 20 A [1] 30 A [2] 50 A [3] 20 … ・ データを順番に並べる ・ 添え字でアクセスする ・ となりの要素の位置を ポインタとして持つ

前回の復習 その他のデータ構造 スタック (stack) 待ち行列 (queue，キュー) 木 (tree) 来週 enqueue push pop 30 30 50 50 20 dequeue 20 3 ・ L I FO ( Last-In First-Out ) ・ F I FO ( First-In First-Out ) 木 (tree) 来週

１つのスタックだけを用いて出力可能なデータ列はどれか ア. イ. ウ. エ. (H16年度 春) A, D, B, C B, D, A, C 練習：　スタック A, B, C, D の順に到着するデータに対して、 １つのスタックだけを用いて出力可能なデータ列はどれか ア. イ. ウ. エ. (H16年度 春) A, D, B, C B, D, A, C C, B, D, A D, C, A, B ウ A B C A B C A B ウ A A B A D A D A

アルゴリズム アルゴリズム 問題を解決するための、有限ステップからなる手順 自然言語や、流れ図（フローチャート）で示す 生協に行く 棚のチョコレートを手に持つ レジに行く 財布から代金を払う お釣りがあれば、受け取る チョコレートを食べる 開 始 1 → i Yes i > n No Yes A(i) = K No 探索成功の処理 探索失敗の処理 i + 1 → i 終 了

流れ図 （フローチャート） 制御の流れを図で表したもの 基本的な記号 繰り返しの開始と終了 （ループ名、終了条件を 開始や終了 記述） 処理 参考： その他の記号 処理の流れ データの入出力 条件に応じて、 次の処理を変える （分岐条件を記述） 書類を印刷 ディスプレイに表示

アルゴリズム： 線形探索 (linear search) ________________ 配列を先頭から順番に探索する 探索キーと同じキーが 配列の中に見つかれば 探索成功 最後まで行っても 見つからなければ 探索失敗 探索キー （探索データ） 70 A [1] 30 A [2] 50 A [3] 20 A [4] 70 A [5] 10 …

アルゴリズム： 線形探索 (linear search) 配列を先頭から順番に探索する n 100 開 始 n： 配列の要素数 K： 探索キー K 70 1 → i i Yes A(i) = K No A [1] 30 i + 1 → i A [2] 50 Yes A [3] 20 i > n No A [4] 70 探索失敗の処理 探索成功の処理 A [5] 10 終 了 …

アルゴリズムの性能評価 計算量 （時間計算量） 大きさ n の入力に対して、 最悪の場合に必要な計算時間 例） 線形探索 A [1] 30 50 最悪の場合、 n 個全部 調べてね A[1] の探索は簡単だから アルゴリズムの 計算時間は一瞬？ A [3] 20 A [4] 70 A [5] 10 …

アルゴリズムの性能評価 計算量 （時間計算量） 大きさ n の入力に対して、 最悪の場合に必要な計算時間 O （オーダ）表記をして、定数倍は無視する 例） 線形探索 ・ 最悪の場合、n 個全部調べる ・ １個調べるには、３つの処理 計算時間 = 3 n … O(n)

アルゴリズム： ２分探索 (binary search) ________________ キーがソートされた配列に対し、高速に探索できる 探索キーと配列中央のキーを比較 A [ ] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 2 5 10 35 50 70 100 110 150 190 191 200 300 400 探索キー 70 同じなら 探索キー ＜ 中央のキー 探索キー ＞ 中央のキー … 探索成功 … 前半分を探せばよい … 後半分を探せばよい

アルゴリズム： ２分探索 (binary search) K： 探索キー n 15 開 始 K 70 1 → L n → H L → M L + H 2 （小数点以下 切り捨て） M ＞ ＝ H A(M) = K ＜ A [1] 1 探索成功の処理 M - 1 → H M + 1 → L A [2] 2 A [3] 5 No A [4] 10 L > H A [5] 35 Yes A [6] 50 探索失敗の処理 A [7] 70 終 了 …

アルゴリズム： ２分探索 (binary search) 計算量 １回調べるごとに、探索範囲は半分になる 最悪でも、log 2 n + 1 回調べれば良い 計算量は O( log n ) A [ ] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 2 5 10 35 50 70 100 110 150 190 191 200 300 400 探索キー 70

補足説明：　 ２ ｎ と ｌｏｇ 2 ｎ 0 回 1 0 回 1 回 2 回 3 回 4 回 5 回 6 回 log 2 n 回 … 1 2 4 8 16 32 64 2 倍 n 2 倍 1 回 2 2 倍 2 回 4 2 倍 3 回 8 2 倍 4 回 16 2 倍 5 回 32 2 倍 6 回 64 2 倍 … … 2 倍 n 回 2 n

アルゴリズムの性能評価 (比較) 計算量 （時間計算量） O （オーダ）表記をする 例) 線形探索 O( n ) アルゴリズムの性能評価 (比較) 計算量 （時間計算量） O （オーダ）表記をする 例) 線形探索 O( n ) ２分探索 O( log n ) O(1) < O( log n ) < O( n ) < O( n log n ) < O( n2 ) < … 50 40 n2 n log n n 30 20 10 log n n 10 20 30 40 50

アルゴリズム： バブルソート (隣接交換法) アルゴリズム：　 バブルソート (隣接交換法) ________________ 隣り合うデータを見比べて、大小関係が逆なら交換 確定 小 20 20 20 20 1 大小がバラバラ 30 30 30 1 20 バラバラ 5 5 1 30 30 10 見比べて交換 1 5 5 5 大 1 10 10 10 10 1 1 1 20 20 5 確定 … 30 5 20 バラバラ 5 30 30 10 10 10

アルゴリズム： バブルソート (隣接交換法) 基本情報技術概論（第５回） 2008/5/22 アルゴリズム：　 バブルソート (隣接交換法) 計算量 1 確定 1 1 1 20 5 確定 5 5 … n 個 30 20 10 確定 10 5 30 20 20 10 10 30 30 １個目を確定させるのに 比較が n – 1 回 ２個目 n – 2 回 ３個目 n – 3 回 … n - 1 個目 1 回 … 全部で O( n2 )

配列 A[ i ] ( i = 1, 2, ..., n ) を、次のアルゴリズムにより 練習：　ソート 配列 A[ i ] ( i = 1, 2, ..., n ) を、次のアルゴリズムにより 整列（ソート）する。行 2 ～ 3 の処理が初めて終了した時、 必ず実現されている配列の状態はどれか。 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 ] を交換する (H19年度 春) ア ア. ウ. A[ 1 ] が最小値になる A[ n ] が最小値になる イ. エ. A[ 1 ] が最大値になる A[ n ] が最大値になる

アルゴリズム： マージソート (併合ソート） アルゴリズム：　 マージソート (併合ソート） ソートされた２つの列 → １つにマージ（併合）するのは簡単 　　（各列の先頭を見比べながら、小さい方を取っていく） １回のマージの実行時間は、要素数に比例 5 20 25 50 1 10 30 40

アルゴリズム： マージソート (併合ソート） アルゴリズム：　 マージソート (併合ソート） 5 25 50 20 30 40 10 1 5 25 50 20 30 40 10 1 分割 5 25 50 20 30 40 10 1 5 25 50 20 30 40 10 1 5 25 20 50 30 40 1 10 マージ log n 段 1 段に O( n ) 時間 → 全部で O( n log n ) 時間

１つのスタックだけを用いて出力可能なデータ列はどれか ア. 練習：　スタック A, B, C, D の順に到着するデータに対して、 １つのスタックだけを用いて出力可能なデータ列はどれか ア. (H16年度 春) A, D, B, C B C A A B B C D B C D

１つのスタックだけを用いて出力可能なデータ列はどれか イ. 練習：　スタック A, B, C, D の順に到着するデータに対して、 １つのスタックだけを用いて出力可能なデータ列はどれか イ. (H16年度 春) B, D, A, C A B A B A C A A C D A C D

１つのスタックだけを用いて出力可能なデータ列はどれか エ. 練習：　スタック A, B, C, D の順に到着するデータに対して、 １つのスタックだけを用いて出力可能なデータ列はどれか エ. (H16年度 春) D, C, A, B A B C D A B C A B A A B C D A B C

ループの中の比較回数を減らす n 100 n： 配列の要素数 K： 探索キー 開 始 K 70 i 1 → i K → A(n+1) Yes アルゴリズム：　番兵付き の 線形探索 ループの中の比較回数を減らす n 100 n： 配列の要素数 K： 探索キー 開 始 K 70 i 1 → i K → A(n+1) Yes A [1] 30 A(i) = K Yes No i > n A [2] 50 No A [3] 20 i + 1 → i A [4] 70 探索成功の処理 探索失敗の処理 A [5] 10 終 了 …

アルゴリズム： 線形探索 (linear search) 配列を先頭から順番に探索する n 100 開 始 n： 配列の要素数 K： 探索キー K 70 1 → i i Yes i > n A [1] 30 No Yes A [2] 50 A(i) = K A [3] 20 No 探索成功の処理 探索失敗の処理 A [4] 70 i + 1 → i A [5] 10 終 了 …

この文面は、TOKYO TECH OCW の利用 条件を参考にしました この教材のご利用について この教材は、以下に示す利用条件の下で、著作権者にわざわざ許諾を求めることなく、無償で自由にご利用いただけます。講義、自主学習はもちろん、翻訳、改変、再配布等を含めて自由にご利用ください。 非商業利用に限定 この教材は、翻訳や改変等を加えたものも含めて、著作権者の許諾を受けずに商業目的で利用することは、許可されていません。 著作権の帰属 この教材および教材中の図の著作権は、次ページ以降に示す著作者に帰属します。この教材、または翻訳や改変等を加えたものを公開される場合には、「本教材 (or 本資料) は http://www.al.ics. saitama-u.ac.jp/horiyama/OCW/ の教材です (or 教材を改変したものです」 との旨の著作権表示を明確に実施してください。なお、この教材に改変等を加えたものの著作権は、次ページ以降に示す著作者および改変等を加えた方に帰属します。 同一条件での頒布・再頒布 この教材、または翻訳や改変等を加えたものを頒布・再頒布する場合には、頒布・再頒布の形態を問わず、このページの利用条件に準拠して無償で自由に利用できるようにしてください。

この教材のご利用について 配布場所 http://www.al.ics.saitama-u.ac.jp/horiyama/OCW/ この powerpoint ファイルの著作者 堀山 貴史　2007-2009 horiyama@al.ics.saitama-u.ac.jp 改変等を加えられた場合は、お名前等を追加してください 図の著作者 p. 4, 7, 9, 10, 11, 13, 18, 22 ～ 24 クリップアート : Microsoft Office Online / クリップアート その他 堀山 貴史