アルゴリズムとデータ構造

講義 アルゴリズムとデータ構造 第 2 回アルゴリズムと計算量 大学院情報科学研究科情報理工学専攻情報知識ネットワーク研究室喜田拓也 講義資料 2018/5/23

今日の内容 アルゴリズムの計算量とは? 漸近的計算量オーダーの計算の方法最悪計算量と平均計算量 ポイント オーダー記法 ビッグオー (O), ビッグオメガ (Ω), ビッグシータ (Θ) 2

お風呂スケジューリング問題 お風呂に入る順番を決めよう! ww 1 時間 ww 2 ww 3 ww 4 全員の待ち時間と入浴時間の合計を最小にする順番を求める 3

お風呂スケジューリング問題 例えば, こんな順番だと 待ち時間 入浴時間 ww 3 0 ww 3 ww 2 ww 3 ww 2 ww 4 ww 3 + ww 2 ww 4 ww 1 ww 3 + ww 2 + ww 4 ww 1 もっと小さくできます ww 1 + 3ww 2 + 4ww 3 + 2ww 4 4

お風呂スケジューリング問題 お風呂に入る順番を決めよう! ww 1 ww 2 時間 私も! お父さんの入った浴槽に浸かりたくない! ww 3 ww 4 お姉ちゃんよりは後でいいや 複雑な制約が付くと, スケジューリング問題はとても難しい! 5

よいアルゴリズムとは? 性能の指標はいろいろある計算時間 メモリサイズ ( 使用メモリ量 ) 外部記憶への入出力数 ネットワークの通信量 ほかの要素再利用可能性 (Reusability) 読みやすさ (Readability) 移植しやすさ (Portability) etc... ここでは, 計算時間とメモリサイズのみに注目する 6

計算コスト ( 計算量 ) という考え方 時間計算量 (time complexity) 計算のステップ数 領域計算量 (space complexity) 記憶領域量 ある問題を解くために必要な計算量を測りたい でも計算時間やメモリサイズはいろいろな要素に依存する! 1. アルゴリズムの方式 2. コーディングスタイル 3. 言語の種類とコンパイラの質 4. ハードウェアの性能 5. 入力そのもの 7

1 個の問題に対して入力は様々 問題例 1 解 1 アルゴリズム 問題例 2 解 2 1 個の問題 = 無限個の問題例の集合 問題 : 最大公約数を求める問題 (GCD) 入力 : 正整数 aa 0, aa 1 出力 :aa 0 と aa 1 の最大公約数 問題例 : (aa 0, aa 1 ) = (28,12), (987654321, 123456789) 8

計算量の評価法 問題例の規模によって計算量が変わる 問題例の規模に応じた評価 入力長 nnの関数 TT(nn) として計算量を評価ただし, 入力長および計算量は計算コストモデルに依存定数 ( 一様 ) コストモデルすべての数を1 語 (1 単位のデータ ) とみなして どの基本命令も単位時間で実行できると仮定対数コストモデル各々の数は, それを表現するのに必要なビット数の語数が必要であり 基本命令の実行はビット数に応じた時間がかかると仮定 大きな数字を扱うことが本質的な問題は対数コストモデル そうでない場合は定数コストモデルで考えることが多い 9

オーダー 記法について ビッグオーダーとかグランドオーダーとか?

漸近的計算量 オーダー評価とは計算量 TT(nn) は十分大きな nn に対して評価する定数倍の差はないものとみなす 定義 [ 漸近的上界 ( ビッグオー記法 )] TT(nn) = O(ff(nn)) ある実数 cc > 0 と自然数 nn 0 が存在して全ての nn nn 0 に対して TT nn cc ff(nn) が成り立つ TT(nn) は, オーダー ff(nn) である または TT(nn) は, ビッグオー ff(nn) である と読む 漸近的上界 (asymptotic upper bound)= 意味 関数 TT(nn) は ff(nn) と同じか小さい 漸近的上界はいくらでも存在するができるだけ単純で精度のよいものがよい (1) 2nn 2 + 5nn + 1000 = O(nn 2 ) best! (2) 2nn 2 + 5nn + 1000 = O(nn 2 + nn) (1) より複雑 (3) 2nn 2 + 5nn + 1000 = O(nn 3 ) (1) より精度が悪い 11

なぜ計算時間をオーダーで測るのか? 質問 : 問題のサイズを大きくしていったらどうなるか? 100nn, 5nn 2, nn 3 /2, 2 nn の計算時間をもつ 4 つのプログラムに対して, その入力 nn を増やしながら走らせたときの計算時間のグラフ オーダーが大きいほど, 係数によらず計算時間が急速に増加する 12

なぜ計算時間をオーダーで測るのか? 質問 : 時間をかけた分だけ大きなサイズの問題が解けるか? 実行時間 TT(nn) 10 3 秒で解ける最大問題サイズ O(nn) 時間アルゴリズムなら計算時間を 10 倍にすると 10 倍の サイズの問題が解ける 10 4 秒で解ける最大問題サイズ 増大率 ( 倍 ) 100nn 10 100 10.0 5nn 2 14 45 3.2 nn 3 /2 12 27 2.3 2 nn 10 13 1.3 しかし,O(nn 3 ) 時間なら 2.3 倍,O(2 nn ) 時間なら 1.3 倍しか 大きくならない! 13

漸近的計算量の性質 TT 1 nn = O ff nn, TT 2 nn = O gg nn のとき, 次の等式が成立 1. TT 1 (nn) + TT 2 (nn) = O max ff nn, gg nn 意味 : いくつかの処理を順次行う場合は一番遅い処理が全体の処理速度を支配する 2. TT 1 nn TT 2 (nn) = O ff nn gg nn 意味 : 処理を繰り返し行うとその回数分時間がかかる ( 例 ) nn 2 + nn 3 = O nn 3, nn 2 nn 3 = O nn 5 証明してみよう! オーダー表記の注意点 : ( 左辺の精度 ) ( 右辺の精度 ) ( 例 ) 2nn 2 + 5nn + 1000 = O nn 2 O(nn 2 ) = 2nn 2 + 5nn + 1000 14

漸近的下界 定義 [ 漸近的下界 ( ビッグオメガ記法 )] TT(nn) = Ω(ff(nn)) ある実数 cc > 0 と自然数 nn 0 が存在して全ての nn nn 0 に対して TT nn cc ff(nn) が成り立つ 漸近的下界 (asymptotic lower bound)= 意味 関数 TT(nn) は ff(nn) と同じか大きい TT(nn) はビッグオメガ ff(nn) である と読む ( 例 ) TT nn = 2nn 2 + 5nn + 1000 = Ω nn 2 TT nn = nn2, nn 3, if nnは奇数 if nnは偶数 TT(nn) = Ω nn 2 下の定義では Ω nn 3 次の定義を Ω の定義として採用することもある ( 研究論文ではこちらも多い ) 上の定義の方が厳しいので上の定義を満たせば次の定義も満たす 漸近的下界の別定義 TT(nn) = Ω(ff(nn)) ある実数 cc > 0 が存在して, 無限個の nn に対して TT nn cc ff(nn) が成り立つ 15

漸近的にタイトな限界 定義 [ 漸近的にタイトな限界 (asymptotic tight bound)] TT(nn) = Θ(ff(nn)) ある実数 cc 0, cc 1 > 0 と自然数 nn 0 が存在して全ての nn nn 0 に対して, cc 0 ff nn TT nn cc 1 ff nn が成り立つ TT(nn) はビッグシータ ff(nn) である と読む ( 例 ) TT nn = 2nn 2 + 5nn + 1000 = Θ nn 2 TT nn = nn2, if nnは奇数 nn 3, if nnは偶数 TT nn Θ nn 3 一般に TT(nn) = Θ(ff(nn)) TT(nn) = O(ff(nn)), TT(nn) = Ω(ff(nn)) Ω の別定義であれば のみ成立 16

( 上級編 ) 教養として o と ω も知っておこう! 定義 [ 漸近的にタイトでない上界 ] TT(nn) = o(ff(nn)) 任意の実数 cc > 0 に対し, ある自然数 nn 0 が存在して, 全ての nn nn 0 に対して TT nn cc ff nn が成り立つ TT(nn) はスモールオー ff(nn) である と読む TT(nn) はnnが無限大に近づくにつれて,ff(nn) に対して相対的に小さくなる T nn すなわち, lim = 0 となる TT(nn) はff(nn) より真に小さい nn ff nn ( 例 ) 2nn = o nn 2, 2nn 2 o nn 2 定義 [ 漸近的にタイトでない下界 ] TT(nn) = ωω(ff(nn)) 任意の実数 cc > 0 に対し, ある自然数 nn 0 が存在して, 全ての nn nn 0 に対して TT nn cc ff nn が成り立つ TT(nn) はスモールオメガff(nn) である と読む TT(nn) はnnが無限大に近づくにつれて,ff(nn) に対して相対的に大きくなる T nn すなわち, lim = となる TT(nn) はff(nn) より真に大きい nn ff nn ( 例 ) 2nn 2 = ωω nn, 2nn 2 ωω nn 2 TT(nn) = o(ff(xx)) ff(xx) = ωω(tt(nn)) 17

オーダーの計算の基本 規則 1: TT(nn) が nn の多項式ならば, 最大次数の項のオーダーになる ( 例 ) 2nn 2 + 3nn + 100 = O nn 2 10nn + 2 nn + 5 = 10nn 1 + 2nn 0.5 + 5 = O nn 規則 2: 次のオーダーの式が成立する log nn = O(nn) nn = O 2 nn 任意のcc > 0に対して,log nn = O nn cc 規則 3: TT(nn) がいくつかの項の和ならば, 最大次数の項のオーダーになる ( 例 ) 3nn 2 + 2 nn + 100 log nn + 5 = O nn 2 18

増加のオーダーによる比較 (1) 計算時間が TT 1 nn と TT 2 nn のアルゴリズムではどちらが速いか? 増加のオーダーが小さい方が速い 規則 4: TT 1 (nn) よりも TT 2 (nn) の方が増加のオーダーが大きい TT lim 1 nn = 0 lim TT 2 nn nn TT 2 nn nn TT 1 nn = 規則 5: TT 1 (nn) と TT 2 (nn) は増加のオーダーが等しい TT 1 nn = Θ T 2 nn TT 2 nn = Θ TT 1 nn TT 1 (nn) とTT 2 (nn) は増加のオーダーが等しい あるcc > 0が存在し TT, lim 1 nn nn TT 2 nn 注意 = cc 19

増加のオーダーによる比較 (2) 規則 6: ロピタル (de l Hospital) の法則 1. ff(xx) とgg(xx) が微分可能で,ff(aa) = gg(aa) = 0かつxx = aa 以外でgg xx 0 ff xx であるなら,lim = lim ff xx が成り立つ xx aa gg xx xx aa gg xx 2. ff(xx) とgg(xx) が微分可能で, lim ff(xx) = lim gg(xx) = であれば, xx xx ff xx lim = lim ff xx が成り立つ xx gg xx xx gg xx ( 例 ) nn 0.01 と log nn 100 ではどちらが漸近的に増加率が大きいか? lim nn log nn 100 nn 0.01 = lim nn 100 log nn 99 1/nn 0.01nn 0.99 = lim nn 100 log nn 99 0.01nn 0.01 = lim nn 100 99 log nn 98 0.01 2 nn 0.01 = = lim nn 100! 0.01 100 nn 0.01 = 0 20

発展問題 次のオーダー表記を簡略化せよ (a) O nn log nn + nn 2 + O nn 1.83 log nn 明らかに nn log nn < nn 2, nn log nn < nn 1.83 log nn である. また, nn 1.83 log nn lim nn nn 2 log nn = lim = lim nn nn0.17 nn 1/nn = lim 0.17nn 0.83 nn よって, 十分大きな nn に対して nn 1.83 log nn < nn 2 であるから O nn log nn + nn 2 + O nn 1.83 log nn = O nn 2 となる. (b) O nn log nn + nn 100 + nn 30 log nn nn 30 log nn < nn 100 は明らか. また十分大きな nn に対して,nn 100 < nn log nn が成り立つ. よって, O nn log nn + nn 100 + nn 30 log nn = O nn log nn となる. 1 = 0. 0.17nn0.17 (c) O(nn 3 sin 2 nn)o(2 nn / log nn) チャレンジ! 21

アルゴリズムの計算量 計算量を問題例の入力長 nn の関数としてオーダー評価したもの以下の二つの評価法がある 最悪計算量 (worst case complexity) 入力長が nn である問題例の中で最大の計算量平均計算量 (average case complexity) 入力長が nn である問題例の計算量の期待値 ( 例 ) 入力長が N の問題例に対し確率 (nn 1)/nn で O nn, 確率 1/nn で O nn 2 であるようなアルゴリズムの計算量 最悪時間計算量 O nn 2 平均時間計算量 O nn 通常は, 最悪計算量で評価することが多い 22

お風呂スケジューリング問題の計算量は? お風呂に入る順番を決めよう! ww 1 ww 2 時間 nn 人のお風呂スケジューリング問題の 解の空間は nn! ( 順列通り ) もある! 単純な方法だと O nn! 時間かかるが うまくやれば O nn log nn 時間で解ける! ww 3 ww 4 全員の待ち時間と入浴時間の合計を最小にする順番を求める 23

今日のまとめ アルゴリズムの計算量とは? 時間計算量と領域計算量入力長 nn の関数 TT(nn) として計算量を評価 オーダー記法漸近的計算量 ( 十分大きな nn で. 定数倍は無視 ) ビッグオー (O), ビッグオメガ (Ω), ビッグシータ (Θ), スモールオー (o), スモールオメガ (ωω) オーダーの比較の仕方, 簡略化の方法 最悪計算量と平均計算量 24