エージェントを管理するボスの苦悩 問題 n人のエージェントを部下に持つボスがいる． エージェントは出張・帰還を頻繁に繰り返す． 手元に残っている部下の管理をどうする？ 手元に残っている部下を配列に保存 1 2 3 4 5 6 7 8 9 10 Gi Je Bu Gu Gu Za Re Za Gu Do Do Ki Za Ki Ve Do Ve Na Ki Ve Ra Na Ra Na Re Ra Re 出張 Bu 帰還 Za 出張 Ve 出張 Gi 出張 Do 帰還 Bu 出張 Gu 出張 Je 出張 Ki 帰還 Na 出張 Ra 出張 Re 帰還 Gu 帰還 Ki 出張 Do 出張 Za 帰還 Gi 帰還

配列でエージェントを管理する利点・欠点 i番目のエージェントの発見 エージェントの発見 O(n) O(1) エージェントの削除 O(n) エージェントの挿入 O(n) 手元に残っている部下を配列に保存 1 2 3 4 5 6 7 8 9 10 Gi Je Gu Bu Za Re Gu Gu Za Do Do Za Ki Ki Do Ve Ve Na Ki Ra Na Ve Na Re Ra Ra

リンクリスト（Linked List）でエージェントを管理 1 2 3 4 5 6 7 8 9 10 配列で管理 Gi Je Gu Bu Gu Re Za Za Gu Do Do Za Ki Ve Ki Do Na Ki Ve Na Ve Ra Na Ra Re Ra Linked Listで管理 スタート Re Za Bu Gu Gi Do Ve Je Re Re 出張 Ki Na Bu 出張 Ra Re 帰還

Linked Listでエージェントを管理する利点・欠点 エージェントの削除 O(1) エージェントの発見 O(n) エージェントの挿入 O(1) i番目のエージェントの発見 O(n) Linked Listで管理 スタート Za Bu Gu Gi Do Ve Je Re Ki Na Ra

配列によるLinked Listの実装 配列による実装 スタート = 0 スタート = 2 再利用 = 2 再利用 = 3 再利用 = -1 再利用 = 2 再利用 = 3 再利用 = -1 再利用 = 3 1 2 3 4 5 6 7 8 9 10 name 配列 Gi Je Gu Re Bu Gu Za Re Za Do Gu Za Do Ki Do Ki Ve Ki Na Ve Na Ra Ve Na Ra Re Ra next 配列 1 4 2 3 Gu 3 4 Za Gu -1 4 5 Za Do Do Ki 6 Ki Ve 7 Na Ve 8 Ra Na 9 10 Re Ra -1 再利用 スタート Za Re Bu Gu Gi Do Ve Je Re Re 出張 Ki Na -1 Bu 出張 Ra Linked Listのイメージ Re 帰還

スパゲッティーソート 手間：①O(n)，②O(n)，③O(1)， ④＋⑤O(n) ，⑥O(n) ②それぞれをxiの長さに切ります． ③テーブルの上にまとめて立てます． ④上から手を下ろし， 　　最初にさわったものを引き抜きます． ⑤それを繰り返します． ⑥最後に，逆に並べます． 手間：①O(n)，②O(n)，③O(1)， 　　　　④＋⑤O(n) ，⑥O(n) Carpenter's algorithm（大工の方法）

エージェントを管理するボスの苦悩 Gi 100000 漠然とした問題 n人のエージェントを部下に持つボスがいる． エージェントは出張・帰還を頻繁に繰り返す． 手元に残っている部下の管理をどうする？ ただし，能力値の高いものを優先的に出張させたい． Re 70000 Je 60000 Bu 60000 Gu 30000 対策: データを配列に保存し並べ替えを利用 データ初期化（並べ替え）→ O(n log n) 出張命令（最適発見・削除） → O(1) 帰還（順番を保ちつつ挿入）→ O(n) Za 23000 Do 22000 もっとうまい手はないか？ 並べ替えはやりすぎな気がする． その時点での最優先要素がわかればよい Ki 18000 Ve 18000 Na 5000 Ra 1500

優先キュー（Priority Queue）という道具 Gi 100000 対策: 高々n個のデータを配列に保存し並べ替えを利用 Re 70000 データ初期化（並べ替え）→ O(n log n) 出張命令（最適発見・削除） → O(1) 帰還（順番を保ちつつ挿入）→ O(n) Je 60000 Bu 60000 対策: 高々n個のデータを優先キューに保存 Gu 30000 データ構造初期化 → O(n log n)（→ O(n)） 出張命令（最適発見・削除） → O(log n) 帰還（優先キューの構造を保ちつつ挿入）→ O(log n) Za 23000 Do 22000 Ki 18000 Ve 18000 Na 5000 Ra 1500

ヒープ（Heap）による優先キューの実現: 定義 Gi 1000 定義【（バイナリ）ヒープ】 ・根付き木 ・各頂点が要素に対応 ・各頂点にはキー値が付属 ・各頂点には高々2個の子要素 ・親の優先順位は子以上 Re 700 Bu 600 → 根の優先順位が最高となる Je 600 Za 230 Ra 15 Na 50 根付き木が深くならないように 気をつける → 上左からつめて入れる Gu 300 Ve 180 Ki 180 Do 220 最大要素数nのとき 木の深さは高々log2n → O(log n)

ヒープによる優先キューの実現: 取り出し操作pop Gi 1000 pop() 根にある要素を取り出す． ヒープの再下右要素を根に移動する． ShiftDown(根の要素)により木を整形する． Re 700 popの計算量はO(log n)である． Bu 600 Je 600 Za 230 Ra 15 Na 50 ShiftDown(x) Gu 300 Ve 180 Ki 180 Do 220 if xの優先度 > xの子の優先度: 優先度の高い子とxの位置を入れ替える ShiftDown(x)

ヒープによる優先キューの実現: 要素の追加push Re 700 push(x) 新しい要素xをヒープの最下右に追加する． ShiftUp(x)によりヒープを整形する． Bu 600 Do 220 pushの計算量はO(log n)である． ShiftUp(x) Je 600 Za 230 Ra 15 Na 50 if xの優先度 > xの親の優先度: xの親とxの位置を入れ替える． ShiftUp(x) 要素数がn個のヒープの構築は ヒープが空の状態から 要素を1つ1つpushすればよいので O(n log n)で完了する． Gu 300 Ve 180 Ki 180 Gi 1000

バケット法（Bucket method）の一例 Gi 123383 <- 120000 バケツ0番～バケツN番を用意 （Nは十分大きい数） キー値がiの要素をバケツi番に入れる Je 56264 <- 100000 Bu 52384 バケツ 52383 Re 59794 <- 70000 Za 23358 バケツ 52385 Do 22265 <- 50000 バケツ 52384 Ki 18159 <- 30000 Ve 18159 バケツ 52383 Na 5310 <- 20000 <- 10000 バケツ 52383 <- 0

ハッシュ法（Hashing）の一例 Gi 123383 (1+2+3+3+8+3) mod 9 = 2 8 Je 56264 7 Bu 52384 (5+2+3+8+4) mod 9 = 4 6 Re 59794 5 (5+9+7+9+4) mod 9 = 7 4 Za 23358 (2+3+3+5+8) mod 9 = 3 3 Do 22265 (2+2+2+6+5) mod 9 = 8 2 Ki 18159 (1+8+1+5+9) mod 9 = 6 1 Ve 18159 (1+8+1+5+9) mod 9 = 6 Na 5310 (5+3+1+0) mod 9 = 0 ハッシュテーブル (Hash table) 各桁の数字を足して9で割った余りを計算 ハッシュ関数（Hash function）