advertisement

Algorithms Introduction 9章

50 %
50 %
advertisement
Information about Algorithms Introduction 9章
Technology

Published on March 8, 2014

Author: mfumi

Source: slideshare.net

advertisement

Introduction to Algorithms : Chapter 9
 Medians and Order Statistics

選択問題 • 入力: n 個の異なる数字の集合Aと整数i ( 1 • 出力: Aのi番目に大きい要素x (x A) i n)

簡単な方法 • ソートしてi番目の要素を取り出す • O(nlogn) (マージソート等)

より良い方法 • 実は O(n) で可能 • この後のスライド 1. 最大/最小値探索問題 (O(n)) 2. 期待実行時間がO(n)のアルゴリズム 3. 最悪実行時間がO(n)のアルゴリズム

最大値/最小値探査問題 最小値(or 最大値) を見つける場合
 → n-1 回の比較が必要
 [証] 1回の比較で1つずつ最小値の候補が減る
 → O(n)
 • 
 
 


同時に最大値/最小値を探索 • 最大値/最小値を両方見つけたい • 単純にやると 2n-2 の比較 • 比較回数を減らす方法 1. 暫定の最大値/最小値を記憶しておく 2. まずまだ比較をおこなっていない2つの要素を比較 3. その結果大きい方を暫定の最大値,小さい方を暫定の最小値と比較 4. 比較回数は3回ですむ

同時に最大値/最小値を探索 • 暫定の最大値/最小値の初期値は • 要素数が奇数の場合: 一番目の要素を暫定の最大 値/最小値とする → 3*floor(n/2)の比較 • 要素数が偶数の場合: 一番目と二番目の要素を比較 し暫定の最大値/最小値を決定 → 3(n-2)/2 の比較 • 結局最大の比較回数はせいぜい floor(3n/2)→Θ(n)

より一般的な問題 A[p..r] から i番目の要素を取り出す
 • 
 
 
 
 
 • クイックソート的な感じ • 期待計算量はΘ(n), 最悪の場合Θ(n^2)

RANDOMIZED_PARTITION() • ピボットの選択をランダムに行い分割する
 → 入力データの分布によらず計算量の期待値が計 算できる

期待計算量を求める • 最悪の場合: p-r-1のサブ配列を再帰的に処理 → Θ(n^2)
 for(i = n;i > 0;i ̶) { for (j = 0; j < i; j++) {分割処理} } • 実際に興味があるのは期待計算量
 T(n) をRANDOMIZED-SELECT()の計算量だとして E[T(n)]を求める • X_k = I{サブ配列A[p..q] が k個の要素を持つ} • E[X_k] = 1/n

期待計算量を求める • X_k = 1 となる k は唯一つのみ • X_k = 1 のときサブ配列は k-1とn-kの要素を持つ
 
 
 
 


期待計算量を求める ここで,
 • 
 
 nが偶数: T([n/2])からT(n-1)は2回ずつ現れる
 nが奇数: T([n/2])が1回,他はT(n-1)が2回現れる


期待計算量を求める 以上より,
 • 
 ここで,E[T(n)] cn を仮定 (c:定数)
 さらに nがある定数以下なら T(n) = O(1)と考え
 O(n)の上限をan (a:定数) で表すとする
 • 
 


期待計算量を求める nが十分大きいとき
 cn/4-c/2-an となればいい 0


期待計算量を求める • cn/4 - c/2 - an い 0→n 2c/(c-4a) になれば良 • このためには c > 4a となる必要がある • T(n)が n < 2c/(c-4a) において O(1)とすれば E[T(n)] = O(n)

より良い方法 : SELECT • 最悪の場合の計算量が O(n)のアルゴリズム: SELECT アルゴリズム 
 (Median of Medians) 1. n個の要素をceil(n/5)のグループに分ける 2. それぞれのグループの中央値を挿入ソートで求める 3. 2. で求めた中央値集合の中央値をSELECTアルゴルズムを再帰的に適用して求 める (求めた値をxとする) 4. 3. で求めた中央値の中央値を使って入力配列を分割する
 具体的にはkが小さい方の配列の要素数+1の数だとすると,xはk番目に小さい 数でn-kの要素が大きい方の配列に入る 5. i == k なら x を返す.i < k なら SELECTアルゴリズムを小さい方の配列に適用, i > k ならSELECTアルゴリズムを大きい方の配列に適用

SELECTアルゴリズム 要素の分割図(矢印: 大きい→小さい) SELECTアルゴリズムでは,良いピボットを選択する

最悪計算量の見積もり step 2 で求めた複数の中央値の半分はxと同じか大きい
 矢印 ceil(n/5) / 2 個のグループのうち最低でも3つの要素はxより小さい (要 素が5個未満の最後のグループを除く).従って,xより大きい要素の数はせい ぜい n- n/5/2*3 = 7n/10
 • 
 
 
 同じように 3n/10-6 個の要素がxより小さい → step 5で最悪の場合 7n/10 + 6 の要素に対して再帰的に処理をおこなう

最悪計算量の見積もり • step1,2,4: O(n) • step3: T(ceil(n/5)) • step5: T(7n/10 + 6) • 要素数が140以下のきはO(1)であると仮定すると
 
 
 
 
 (140 の起源についてはこの後示す)


最悪計算量の見積もり T(n) cn (c:大きな定数)と仮定
 さらに O(n) の上限 をan (a:定数) とする
 • 
 
 
 
 
 -cn/10 + 7c + an 0 なら T(n) cn
 → c 10a(n/(n-70)) (n 70のとき)
 n 140 としたので n/(n-70) 2, c 20aのように選べば上の等 式を満たす
 実際には n は 70より大きければ,cを適切に選べば等式は成り立つ

最悪計算量の見積もり 再掲
 • 
 
 • ポイントは,n/5 + 7n/10 = 9n/10 < n であること • 分割数 x = 5 以外の場合は? 
 → とりあえず xは奇数 (偶数だと中央値に偏りが生じる) • x = 3 の場合:
 T(n) T(n/3) + T(2n/3) + O(n) → n/3+2n/3 = n これは 
 (中央値の中央値x より最低でも n/3/2*2 の要素が大きい → 最大でもn - n/3/2*2 = 2n/3の要 素がxより小さい) • x = 7,9,11,… でも良いが,そうすると分割にかかる時間が増える 
 


まとめ • SELECTアルゴリズムを使えば最悪計算量がO(n)で n個の要素からi番目の要素が取得可能 • SELECTアルゴリズムでは入力の分布に対して何ら かの仮定がいらない • ソートを使う場合 Ω(n log n),
 asymptotically inefficient

Add a comment

Related presentations

Presentación que realice en el Evento Nacional de Gobierno Abierto, realizado los ...

In this presentation we will describe our experience developing with a highly dyna...

Presentation to the LITA Forum 7th November 2014 Albuquerque, NM

Un recorrido por los cambios que nos generará el wearabletech en el futuro

Um paralelo entre as novidades & mercado em Wearable Computing e Tecnologias Assis...

Microsoft finally joins the smartwatch and fitness tracker game by introducing the...

Related pages

Introduction to Algorithms study group

Introduction to Algorithms; Exercise index; About this site; Chapter 01. Section 1: 1.1.1 1.1.2 ... C.3.9 C.3.10 Section 4: C.4.1 C ...
Read more

アルゴリズムイントロダクション 第3版 総合版 (世界標準MIT教科書) | T. コルメン, R. リベスト, C ...

本書は,原著の第1~35章,および付録a~dまでの完訳総合版である.また巻末の索引も圧巻で,和(英)‐英(和) ...
Read more

Distributed Computing: Principles, Algorithms, and Systems ...

「Distributed Computing: Principles, Algorithms, and Systems」の4章 メモリダンプのように、分散システム全体に対する「現在 ...
Read more

Lecture on the Introduction of Algorithms by Hiroshi Ichiji

第1章: 2 : 9/21 : 簡単なプログラミング(2) 関数 : ... 2015年9月22 日改訂 2015年10 ...
Read more

Lower Bound : Note on Algorithms

今回のオススメ本 (アルゴリズムの全体をやさしく解説) Title: Introduction to Algorithms (特に、第9章 Sorting) Author: ...
Read more

MIT_Introduction to Algorithms 算法导论视频字幕 - 下载频道 - CSDN.NET

MIT_Introduction to Algorithms 算法 ... 9 第六课 序列统计,中位数 阅读:9 章 10 演示课 4 中位数的应用,桶式排序 ...
Read more

Introduction to Algorithms 算法导论 第2章 算法入门 学习笔记及习题解答 - cppgp ...

最新评论. Introduction to Algorithms 算法导论 第2章 算法入门 学习笔记及习题解答. Jofranks: y = a + y * x = a + (a * x + a * x ...
Read more

Introduction to Algorithms - 百度百科 全球最大 ...

《Introduction to Algorithms》译作《算法导论》,是由Thomas H.Cormen, Charles E.Leiserson ... 第9章 中位数和顺序 ...
Read more

算法导论第1章_文库下载 - wenkuxiazai.com

算法导论第一章-introduction (1) ... 算法导论,第一章计算机算法导论,第一章隐藏>> Introduction to Algorithms ... 算法导论第9章.
Read more