Presentation is loading. Please wait.

Presentation is loading. Please wait.

データ構造と アルゴリズムI 第三回 知能情報学部 新田直也.

Similar presentations


Presentation on theme: "データ構造と アルゴリズムI 第三回 知能情報学部 新田直也."— Presentation transcript:

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


Download ppt "データ構造と アルゴリズムI 第三回 知能情報学部 新田直也."

Similar presentations


Ads by Google