基本情報技術概論 I (第11回) アルゴリズム と データ構造 埼玉大学 理工学研究科 堀山 貴史 1 前回までの復習： データ構造 基本的なデータ構造 配列 (array) リスト (list) その他のデータ構造 スタック (stack) 待ち行列 (queue, キュー) 木 (tree)、２分木 (binary tree) ２分探索木、ヒープ この後、すぐ 2 前回までの復習： アルゴリズム 問題を解決するための、有限ステップからなる手順 （言葉やフローチャートなどで書く） 線形探索 (linear search) 探索キー 70 A[ ] 1 2 1 2 3 4 5 6 7 8 9 10 5 10 35 50 70 100 110 150 … 先頭から順番に調べる 大きさ n の配列の探索時間 （計算量） O( n ) 3 前回までの復習： A[ ] 1 2 1 2 アルゴリズム ２分探索 (binary search) 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 ソートされた配列に対し、高速に探索できる 探索範囲の中央を調べる → 探索キーとの比較で、探索範囲が半分に 計算量 … O( log n ) 4 データ構造： 木 深さ 0… (tree) 節点 と 辺 （枝 ともいう） からなり 以下の １、２ を満たすもの 1… 2… 3… 1. すべての節点が連結である 2. サイクルを持たない 葉 先祖 親 この節点から見て 子 根 兄弟 子孫 5 データ構造： ２分木 (binary tree) ___________ 各節点の子は、高々２つ 右の子 と 左の子 は、区別する 例) 下の３つは、どれも異なる２分木 完全２分木 … 20 個 … 21 個 … 22 個 6 ２分木の実現法 リスト 2 1 4 2 5 深さ 0 5 7 7 配列 A[ ] 1 3 3 4 1 2 3 1 4 5 6 2 7 節点 i の 左の子 2i 右の子 2i + 1 親 i /2 ________ 7 ___________ ２分探索木 8 データ構造： ２分探索木 ___________ ２分木の各節点に、データを格納 節点 v のデータは (1) v のどの左の子孫よりも大きい (2) v の 〃 右 〃 小さい 例） 6 3 最小 → 1 10 4 8 12 ← 最大 7 9 ２分探索木の操作 探索 探索キー 8 6 3 1 10 4 8 12 7 根から出発 探索キー = 節点のキー … 探索成功 探索キー < 節点のキー … 左の部分木へ 探索キー > 節点のキー … 右の部分木へ 10 ２分探索木の操作 追加 9 を追加 6 3 1 10 8 4 7 12 9 探索と同様にして、木をたどる 木から飛び出したところに、新しい節点を加える 11 ２分探索木の操作 削除 10 を削除 6 3 1 10 4 8 12 7 削除するキーを探索して削除 ２分探索木の条件に合うように移動 （子孫も同様） 左部分木の最大値を移動 or 右部分木の最小値を移動 12 ___________ ヒープ 13 データ構造： ヒープ (heap) ___________ 完全２分木の各節点に、データを格納 親と子の大小関係をそろえる (ヒープ ソートに利用) 親 > 子 なら、根が最大 親 < 子 なら、根が最小 例） ２分探索木との 9 違いに注意 6 3 7 2 4 1 14 ヒープの操作 探索 最大値は？ 7 6 3 5 2 4 1 ヒープ ソート 値を順に追加 最大値を順に取り出す (最大値を探索 & 削除) 15 ヒープの操作 追加 8 を追加 7 6 3 5 2 4 1 8 ヒープの最後 (深さ最大、左詰め) に新しい節点を追加 ヒープの維持 16 ヒープの操作 削除 7 1 6 3 5 2 4 6 1 3 5 2 4 7 を削除 ヒープの最後を削除する節点に追加移動 ヒープの維持 17 データ構造： ２分木 ２分探索木 ヒープ 木 (tree) まとめ 左の子孫 < 親 < 右の子孫 親 > 子 (または 親 < 子) バランス木 部分木の節点数や深さにバランスを 完全バランス木 左右の部分木の節点数の差が１以内 AVL 木 左右の部分木の深さが１以内 多分木 B 木 (各節点が最大 m 個の子をもつバランス木) 18 19 20 アルゴリズム： バブルソート (隣接交換法) 隣り合うデータを見比べて、大小関係が逆なら交換 小 大 小 が バ ラ 大 バ ラ 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 ラ … 21 アルゴリズム： 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 ) 22 アルゴリズム： ヒープソート (heap sort) ヒープの最大値の取り出し、ヒープの維持を繰り返す 7 1 6 5 6 3 2 4 1 最大値の取り出し 5 6 3 2 4 1 7 最後の葉の移動 3 7 2 4 ヒープの維持 4 6 3 5 5 7 1 2 4 最大値の取り出し 3 5 67 1 2 4 最後の葉の移動 3 1 5 67 2 ヒープの維持 23 アルゴリズム： ヒープソート (heap sort) ヒープの最大値の取り出し、ヒープの維持を繰り返す 7 6 1 5 6 3 2 4 1 最大値の取り出し 計算量 O( 1 ) 3 5 7 2 4 ヒープの維持 計算量 O( log n ) n 回 繰り返し … トータルの計算量 O( n log n ) 24 アルゴリズム： マージソート ソートされた２つの列 → １つにマージ（併合）するのは簡単 （各列の先頭を見比べながら、小さい方を取っていく） 5 20 25 50 (併合ソート） 1 10 30 40 １回のマージの実行時間は、要素数に比例 25 アルゴリズム： マージソート (併合ソート） 5 25 50 20 30 40 10 1 5 25 50 20 5 25 5 25 5 25 30 40 10 1 50 20 50 20 20 50 30 40 30 40 30 40 分割 10 1 10 log n 段 1 1 10 マージ log n 段 1 段に O( n ) 時間 → 全部で O( n log n ) 時間 27 28 この教材のご利用について この文面は、TOKYO TECH OCW の利用 条件を参考にしました この教材は、以下に示す利用条件の下で、著作権者にわざわざ許諾を 求めることなく、無償で自由にご利用いただけます。講義、自主学習は もちろん、翻訳、改変、再配布等を含めて自由にご利用ください。 非商業利用に限定 この教材は、翻訳や改変等を加えたものも含めて、著作権者の許 諾を受けずに商業目的で利用することは、許可されていません。 著作権の帰属 この教材および教材中の図の著作権は、次ページ以降に示す著 作者に帰属します。この教材、または翻訳や改変等を加えたもの を公開される場合には、「本教材 (or 本資料) は http://www.al.ics. saitama-u.ac.jp/horiyama/OCW/ の教材です (or 教材を改変したものです」 との旨の著作権表示を明確に実施 してください。なお、この教材に改変等を加えたものの著作権は、 次ページ以降に示す著作者および改変等を加えた方に帰属しま す。 同一条件での頒布・再頒布 この教材、または翻訳や改変等を加えたものを頒布・再頒布する 場合には、頒布・再頒布の形態を問わず、このページの利用条件29 この教材のご利用について 配布場所 http://www.al.ics.saitama-u.ac.jp/horiyama/OCW/ この powerpoint ファイルの著作者 堀山 貴史 2007-2009 [email protected] 改変等を加えられた場合は、お名前等を追加してください 図の著作者 p. 3, 4, 10 ～ 12, 14 ～ 17 クリップアート : Microsoft Office Online / クリップアート その他 堀山 貴史 30
© Copyright 2024 ExpyDoc
