アルゴリズムとデータ構造 第３回基本的なデータ構造（リスト） 2015/10/28 アルゴリズムとデータ構造　2015

前回の復習(1/3) アルゴリズムの計算量 入力長nの関数T(n)の漸近的計算量で評価 漸近的上界(asymptotic upper bound) 記号O T(n)=O(f(n)) 　⇔　ある実数c>0と自然数n0が存在して 　　　　　　　　　　　　全ての自然数n≧n0に対して 　T(n)≦cf(n)が成り立つ 漸近的下界(asymptotic lower bound) 記号Ω T(n)=Ω(f(n)) 　⇔　ある実数c>0と自然数n0が存在して 　　　　　　　　　　　　全ての自然数n≧n0に対して T(n)≧cf(n)が成り立つ 漸近的にタイトな限界(asymptotic tight bound) 記号Θ T(n)=Θ(f(n)) 　⇔　ある実数c1,c2>0と自然数n0が存在して 　　　　　　　　　　　　全ての自然数n≧n0に対して c1f(n)≦T(n)≦c2f(n)が成り立つ 2015/10/28 アルゴリズムとデータ構造　2015

前回の復習(2/3) 計算時間がT1(n)とT2(n)のアルゴリズムではどちらが速いか？ ⇒漸近的増加率が小さい方が速い T1(n) T1(n)よりもT2(n)の方が漸近的増加率が大きい　⇔　limn→∞ = 0 ⇔　limn→∞　　　　= ∞ T2(n) T1(n) T1(n) T2(n) limn→∞ = 0　から何が言えるか？ 　　　　T1(n)=O(T2(n)), T2(n)=Ω(T1(n)) (タイトではないので、更にT1(n)=o(T2(n)), T2(n)=ω(T1(n))も言える。) limn→∞　　　　= c (0<c<∞)　から何が言えるか？ 　　　　T1(n)=O(T2(n)), T1(n)=Ω(T2(n)), T2(n)=O(T1(n)), T2(n)=Ω(T1(n)) したがって、T1(n)=Θ(T2(n)), T2(n)=Θ(T1(n)) T1(n) T2(n) limn→∞　　　　が存在しない場合でもT1(n)=O(T2(n)), T1(n)=Ω(T2(n)), T1(n)=Θ(T2(n))などであり得る。→元の定義に従って証明する。 T1(n) T2(n) 2015/10/28 アルゴリズムとデータ構造　2015

前回の復習(3/3) 任意のa,b>0に対し 茨木先生の教科書の演習問題 limn→∞ = 0 常に　logan<nb　である。 茨木先生の教科書の演習問題 (5) つぎのオーダー表記を簡略化せよ。 (a) O(nlogn+n2)+O(n1.83logn) 明らかにnlogn<n2, nlogn<n1.83lognである。 　　　また、 　　　　 limn→∞ = limn→∞ = limn→∞ = limn→∞ =0 よって十分大きなnに対してn1.83logn<n2であるから 　　　　O(nlogn+n2)+O(n1.83logn)=O(n2) (b) O(nlogn+n100+n30logn) n30logn<n100は明らか。 　　　また十分大きなnに対してn100<nlognが成り立つ。 　　　よって 　　　　 O(nlogn+n100+n30logn)=O(nlogn) logan nb n1.83logn logn 1/n n2 n0.17 0.17n－0.83 慣れてきたら この知識から 直接結論付けても OK 1 0.17n0.17 (c) O(n3sin2n)O(2n/logn) sin2n≦1であるから 　　 O(n3sin2n)O(2n/logn) 　　　 =O(n32n/logn) 2015/10/28 アルゴリズムとデータ構造　2015

データ構造 データ構造とは セル(cell)の集合にある構造を与えたもの データを格納する基本単位 Algorithms + Data Structures = Programs Niklaus Wirth （二クラウス・ビルト）が書いた本の題名 Niklaus Wirth(1934-)はスイスの計算機科学者。 コンピュータ言語Pascalの設計者。 １９８４年にチューリング賞受賞。 2015/10/28 アルゴリズムとデータ構造　2015

リスト リストとは 要素を０個以上１列に並べたもの （注意）リストは連結リストを指すことが多い [リスト a0,a1,…,an-1の実現法] 　　　　　　　　要素を０個以上１列に並べたもの （注意）リストは連結リストを指すことが多い [リスト　a0,a1,…,an-1の実現法] 1. 配列(array) n個の連続領域に格納 a0 a1 ・・・ an-1 2. 連結リスト(linked list) ポインタで次の要素の格納領域を指す init a0 a1 ・・・ an-1 null 3. 双方向連結リスト(doubly linked list) ポインタで前後の要素の格納領域を指す ・・・ init null a0 a1 an-1 null final ・・・ 2015/10/28 アルゴリズムとデータ構造　2015

C言語によるリストの定義(1/3) 配列 int a[100]; % 100個の整数a[0],a[1],…,a[99]からなる配列 連結リスト struct cell {・・・}： 構造体cellを・・・と定義 typedef ・・・ cell： ・・・をデータタイプcell型 　　　　　　　　　　　　として定義 typedef struct cell { int element; struct cell *next; } cell; cell *init=NULL; 　　 %空のリスト void list_add(int x) { 　　　　　　%整数要素xを先頭へ追加 cell *new=(cell *)malloc(sizeof(cell)); new->element=x; new->next=init; init=new; } initはcell型データを指すポインタ型 sizeof(cell)： cell型のデータサイズ（バイト） malloc(n)：nバイトのメモリーを確保 (cell *)malloc(n)： 確保したnバイトの領域を 　　　　　　　　cell型データ格納領域とみなす。 2015/10/28 アルゴリズムとデータ構造　2015

C言語によるリストの定義(2/3) element領域 typedef struct cell { int element; struct cell *next; } cell; cell *init=NULL; 　　 %空のリスト void list_add(int x) { 　　　　　　%整数要素xを先頭へ追加 cell *new=(cell *)malloc(sizeof(cell)); new->element=x; new->next=init; init=new; } init 3 6 NULL next領域 list_add(5)を実行すると new ①メモリの確保 new ②elementの代入 5 ③nextにinitポインタ 　 をコピー new ④initにnewポインタ 　をコピー 5 init 3 6 init NULL 3 6 2015/10/28 NULL アルゴリズムとデータ構造　2015

C言語によるリストの定義(3/3) typedef struct cell { int element; struct cell *prev; struct cell *next; } cell; cell *init=NULL; 　　 %空のリスト cell *final=NULL; void list_add(int x) { 　%整数要素xを先頭へ追加 cell *new=(cell *)malloc(sizeof(cell)); new->element=x; new->next=init; 　　new->prev=NULL; if(init==NULL) final=new; else init->prev=new; init=new; } 双方向連結リスト cell型は１つ前のデータを指す ポインタprevももつ 最後尾のデータを指す ポインタfinalも必要 先頭に追加する場合は１つ前の データはなし 最初に格納されたデータが最後尾の データ（finalが指すデータ)となる ２つ目以降に格納されたデータは prevポインタを新しい先頭データを 指すように更新する 2015/10/28 アルゴリズムとデータ構造　2015

連結リストが得意な処理（挿入） INSERT(x,p,L) : リストL（要素数n）の位置pの次の位置に要素xを挿入 配列の場合 最悪/平均 a0 a1 ・・・ ai-1 ai ・・・ an-1 最悪/平均 時間計算量はΘ(n) a0 a1 ・・・ ai-1 x ai ・・・ an-1 p 連結リスト の場合 init a0 a1 ai-1 ai ・・・ ・・・ an-1 null init a0 a1 ai-1 ai ・・・ ・・・ an-1 null 最悪/平均時間計算量はΘ(1) x 双方向連結リストの場合 p init final null a0 ・・・ ai-1 ai ・・・ an-1 null ・・・ ・・・ init final null a0 ・・・ ai-1 ai ・・・ an-1 null ・・・ ・・・ 2015/10/28 最悪/平均時間計算量はΘ(1) x アルゴリズムとデータ構造　2015

連結リストが得意な処理（削除） DELETE(p,L) : リストL（要素数n）の位置pの次の位置の次の要素を削除 配列の場合 最悪/平均 a0 a1 ・・・ ai-1 ai ai+1 ・・・ an-1 最悪/平均 時間計算量はΘ(n) a0 a1 ・・・ ai-1 ai+1 ・・・ an-1 p 連結リスト の場合 init a0 ai-1 ai ai+1 ・・・ ・・・ an-1 null init a0 ai-1 ai+1 ・・・ ・・・ an-1 null 最悪/平均時間計算量はΘ(1) 双方向連結リストの場合 p ・・・ ・・・ ai-1 ai ai+1 ・・・ ・・・ ・・・ ai+1 ・・・ ai-1 ・・・ ・・・ 最悪/平均時間計算量はΘ(1) 2015/10/28 アルゴリズムとデータ構造　2015

配列が得意な処理（i番目の要素へのアクセス） FIND(i,L) : リストL（要素数n）のi番目のセルの内容を返す LAST(L) : リストL（要素数n）の最後のセルの位置を返す PREVIOUS(p,L) : リストL（要素数n）において、位置pの１つ前のセルの位置を返す 配列の場合 連続領域であるためi番目の要素や前後の要素に１ステップでアクセス可能 p FIND(i,L) : Θ(1) LAST(L) : Θ(1) PREVIOUS(p,L) : Θ(1) a a0 a1 ・・・ ai-1 ai ai+1 ・・・ an-1 ＝ PREVIOUS(p,L) FIND(i,L) LAST(L) p 連結リスト の場合 init a0 ai-1 ai ai+1 ・・・ ・・・ an-1 null ＝ PREVIOUS(p,L) FIND(i,L) LAST(L) FIND(i,L) : Θ(n), LAST(L) : Θ(n), PREVIOUS(p,L) : Θ(n) 双方向連結リストの場合 p init final null a0 ・・・ ai-1 ai ・・・ an-1 null ・・・ ・・・ ＝ PREVIOUS(p,L) FIND(i,L) LAST(L) FIND(i,L) : Θ(n), LAST(L) : Θ(1), PREVIOUS(p,L) : Θ(1) 2015/10/28 アルゴリズムとデータ構造　2015

配列による連結リストの実現 メリット メモリー確保、解放の時間を節約できる。 メモリー使用量を制御できる。 1 2 3 4 5 6 m-3 m-2 m-1 a1 a0 a2 an-1 ・・・ an-2 2 4 6 1 9 -1 7 ・・・ m-1 5 -1 free_init init 3 メリット メモリー確保、解放の時間を節約できる。 メモリー使用量を制御できる。 ガベージコレクションの必要がない。 2015/10/28 アルゴリズムとデータ構造　2015

スタック(stack) スタックとは 要素の挿入、削除がいつも先頭からなされるリスト LIFO(last-in-fast-out) 　　　　　要素の挿入、削除がいつも先頭からなされるリスト LIFO(last-in-fast-out) [基本操作] TOP(S) スタックSの先頭の位置を返す POP(S) スタックSの先頭の要素を削除 PUSH(x,S) スタックSの先頭に要素xを挿入 a2 PUSH(a2,S) a2 POP(S) a2 TOP(S) a1 a1 a1 a0 a0 a0 2015/10/28 アルゴリズムとデータ構造　2015

スタックの実現法 配列による実現 S すべての操作の 時間計算量はΘ(1) S 連結リストによる実現 すべての操作の 時間計算量はΘ(1) top i =TOP(S) 配列による実現 S a0 a1 ・・・ ai ・・・ PUSH(ai+1,S) すべての操作の 時間計算量はΘ(1) POP(S) top i+1 S a0 a1 ・・・ ai ai+1 ・・・ TOP(S) 連結リストによる実現 = ai-1 top ai ・・・ a0 null PUSH(ai+1,S) POP(S) すべての操作の 時間計算量はΘ(1) top ai ai-1 ・・・ a0 null ai+1 2015/10/28 アルゴリズムとデータ構造　2015

スタックの応用例（関数呼び出し） int factorial(int n) { 1: if n≠1 then goto 3 プログラム int factorial(int n) { if(n==1) return 1; else return n*factorial(n-1); } 実行コードシークエンス 1: if n≠1 then goto 3 2: return 1 3: r=factorial(n-1) 4: return n*r factorial(3) factorial(2) スタック n=3, 戻り:4 局所変数n n 3 2 factorial(1) 3 実行コード 1: 1: n=2, 戻り:4 2: 実行アドレス 2: n=3, 戻り:4 3: 3 3: 3 4: 4: n 1 1: スタック n=3, 戻り:4 2: 2 3: n 3 n 2 4: 6 1: 1: 2: 2: 3: 3: 4: 4 4: 4 2015/10/28 アルゴリズムとデータ構造　2015

待ち行列(キュー, queue) 待ち行列(キュー）とは 要素の挿入は最後尾、削除は先頭からなされるリスト 　　　　　要素の挿入は最後尾、削除は先頭からなされるリスト FIFO(fast-in-fast-out) [基本操作] TOP(Q) キューQの先頭の位置を返す ENQUEUE(x,Q) 要素xをキューQの最後尾に入れる DEQUEUE(Q) 先頭の要素をキューQから除く ENQUEUE(a2,Q) a0 a1 a2 TOP(Q) a0 a1 a2 DEQUEUE(Q) a0 a1 a2 2015/10/28 アルゴリズムとデータ構造　2015

キューの実現法 配列による実現 Q すべての操作の 時間計算量は Q Θ(1) 連結リスト による実現 すべての操作の 時間計算量は TOP(Q) = front j rear (j+i)%n 配列による実現 n-1 Q ・・・ a0 a1 ・・・ ai ・・・ ENQUEUE(ai+1,Q) front j rear (j+i+1)%n すべての操作の 時間計算量は Θ(1) n-1 Q ・・・ a0 a1 ・・・ ai ai+1 ・・・ DEQUEUE(Q) front (j+1)%n rear (j+i+1)%n n-1 ・・・ a1 ・・・ ai ai+1 ・・・ TOP(Q) 連結リスト による実現 = front a0 a1 ・・・ ai null rear ENQUEUE(ai+1,S) a0 a1 ai ai+1 null rear front ・・・ すべての操作の 時間計算量は Θ(1) DEQUEUE(Q) a1 ai+1 null front ・・・ ai rear 2015/10/28 アルゴリズムとデータ構造　2015