Download presentation
Presentation is loading. Please wait.
1
データ構造と アルゴリズムI 第三回 知能情報学部 新田直也
2
プログラムの構成要素 アルゴリズムはプログラムを構成する重要な要素. もう一つの重要な構成要素: →データ構造
データを扱うアプリケーション: データベース,ワープロ,表計算,作図ソフト,メーラー,ゲーム,… 数は最も単純なデータ構造. 自然数,整数,有理数,実数,… 数学におけるより複雑なデータ構造の例. ベクトル,行列,集合,リスト,…
3
数学と情報科学の違い 数学が扱う対象は変化しない. 情報科学が扱う対象(データ)は変化する. 情報科学では,データは操作によって変化する.
3x = 2x + 5 ⇒ x の値は常に5 (x は未知数,代数) 情報科学が扱う対象(データ)は変化する. x = x + 1; ⇒ x の値が1つ増える (x は変数) 情報科学では,データは操作によって変化する. 例えば,集合への操作を考える. 要素の追加,要素の削除,・・・ <データ構造> 操作1 操作2 操作3
4
抽象データ型(1/2) データ構造に応じて操作の内容と種類が定まる.
データ構造とそれに対する操作群をまとめた (カプセル化した)ものを抽象データ型と呼ぶ. 2 2 11 11 13 要素13の追加 5 5 3 3 7 7 要素3の削除 2 11 5 7
5
抽象データ型(2/2) 集合抽象データ型 抽象データ型では, ≪操作≫ ≪データ構造≫ 要素の追加 要素の削除 要素の有無 要素の数を調べる
操作の種類と働きは定義されているが,操作のアルゴリズムは問われない.(正しければ何でもよい.) 具体的なデータ構造も定義されていない. →情報隠蔽と呼ばれる. 集合抽象データ型 ≪操作≫ ≪データ構造≫ 要素の追加 要素の削除 要素の有無 要素の数を調べる 2 11 5 3 7
6
代表的な抽象データ型(1/2) 集合 リスト 要素の追加 要素の削除 要素の有無 要素の数を調べる k番目の位置に要素を追加
11 5 3 7 5 2 7 3 11
7
代表的な抽象データ型(2/2) スタック キュー(待ち行列) 先頭への要素の追加 (push) 先頭からの要素の取り出し (pop)
先頭へ要素を入れる (enqueue) 末尾からの要素の取り出し (dequeue) 頂上(top) 底(bottom) 5 5 2 7 3 11 5 5 2 7 3 11 先頭(front) 末尾(rear) 5 5 2 7 3 11 5 2 7 3 11 11
8
リストのデータ構造 リストを実装可能なデータ構造は何通りもある. まずは配列による実装を考えよう. リストのインターフェースは何だったか?
配列,連結リスト,… まずは配列による実装を考えよう. リストのインターフェースは何だったか? k番目の位置に要素eを追加: insert(k, e) k番目の位置の要素を削除: delete(k) k番目の位置の要素を読む: read(k) k番目の位置の要素にeを上書きする: write(k, e)
9
配列によるリストの実装(1) まずは簡単なものから… int list[1000]; int num = 0; // 要素の数
int read(int k) { if (k < num) return list[k]; return ERR; } void write(int k, int e) { if (k < num) list[k] = e;
10
配列によるリストの実装(2) 続き… deleteは…? void insert(int k, int e) { int n;
if (k <= num) { for (n = num - 1; n >= k; n--) { list[n+1] = list[n]; } list[k] = e; num++; deleteは…?
11
リストを配列で実装した場合の計算量 データのサイズ: 配列の要素数(num). (最悪)時間計算量 read: 2ステップ → O(1)
write: 2ステップ → O(1) insert: k が 0 の場合最悪. (3×num + 3)ステップ → O(num) void insert(int k, int e) { if (k <= num) { for (int n = num - 1; n >= k; n--) { list[n+1] = list[n]; } list[k] = e; num++;
12
計算量のオーダの求め方 正しくは,最悪の場合のステップを計算する必要. どうせ,オーダで表すと係数や定数は捨てられる.
insert の場合,(2×num + 3)ステップ どうせ,オーダで表すと係数や定数は捨てられる. どんぶり勘定でよい. ループの回数,深さに注目する. 基本的に,k重ループがあった場合,オーダはO(nk). もっとも遅い処理だけに注目.
13
連結リスト 各要素がリンクでつながっているリスト 詳細は次回. n番目の要素には先頭からn回リンクをたどらなければたどり着かない. 先頭 5
2 7 3 11 5 2 7 3 11 5 2 7 3 11 5 2 7 3 11
14
連結リストによるリストの実装 read, write: O(n) insert: O(n) delete: O(n) 先頭 5 2 3 11
7 先頭 5 2 7 3 11
15
リストの実装のまとめ 同じ抽象データ型でも内部のデータ構造が変わると操作するアルゴリズムもその計算量も変わる. リストの インタフェース
リストの場合: リストの インタフェース 配列による 実装 連結リストによる実装 read O(1) O(n) write insert delete
Similar presentations
© 2024 slidesplayer.net Inc.
All rights reserved.