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

講義「アルゴリズムとデータ構造」

第２回 アルゴリズムと計算量

大学院情報科学研究科 情報理工学専攻 情報知識ネットワーク研究室 喜田拓也 2018/5/23 講義資料

今日の内容

アルゴリズムの計算量とは？

漸近的計算量

オーダーの計算の方法

最悪計算量と平均計算量

ポイント

オーダー記法

ビッグオー

(O)，ビッグオメガ(Ω)，ビッグシータ(Θ)

2

𝑤𝑤₃ 𝑤𝑤₄ 𝑤𝑤₁ 時間 𝑤𝑤₂

お風呂スケジューリング問題

お風呂に入る順番を決めよう！

全員の

待ち時間

と

入浴時間

の合計を最小にする順番を求める

3

お風呂スケジューリング問題

待ち時間

入浴時間

𝑤𝑤

₁

+ 3𝑤𝑤

₂

+ 4𝑤𝑤

₃

+ 2𝑤𝑤

₄

0

𝑤𝑤

₃

𝑤𝑤

₃

+ 𝑤𝑤

₂

𝑤𝑤

₄

𝑤𝑤

₃

𝑤𝑤

₂

𝑤𝑤

₃

+ 𝑤𝑤

₂

+ 𝑤𝑤

₄

𝑤𝑤

₁ 𝑤𝑤₃ 𝑤𝑤₄ 𝑤𝑤₂ 𝑤𝑤₁ 4

例えば，こんな順番だと

…

もっと小さく できます

𝑤𝑤₁ 𝑤𝑤₃ 𝑤𝑤₄ 時間 𝑤𝑤₂

お風呂スケジューリング問題

お風呂に入る順番を決めよう！

複雑な制約が付くと，スケジューリング問題はとても難しい！

お父さんの入った浴槽に浸かりたくない！

私も！

お姉ちゃんよりは後でいいや

5

よいアルゴリズムとは？

性能の指標はいろいろある

計算時間

メモリサイズ（使用メモリ量）

外部記憶への入出力数

ネットワークの通信量

ほかの要素

再利用可能性

(Reusability)

読みやすさ

(Readability)

移植しやすさ

(Portability)

etc...

6

ここでは，計算時間とメモリサイズのみに注目する

計算コスト（計算量）という考え方

7

時間計算量

(time complexity) ⇒ 計算のステップ数

領域計算量

(space complexity) ⇒ 記憶領域量

ある問題を解くために必要な計算量を測りたい・・・でも

計算時間やメモリサイズはいろいろな要素に依存する！

1. アルゴリズムの方式

2. コーディングスタイル

3. 言語の種類とコンパイラの質

4. ハードウェアの性能

5. 入力そのもの

１個の問題に対して入力は様々

8 問題例１ 解１ 問題例２ 解２

１個の問題 ＝ 無限個の問題例の集合

アルゴリズム

最大公約数を求める問題

(

_GCD

)

入力：正整数

𝑎𝑎

₀

, 𝑎𝑎

₁

出力：

𝑎𝑎

₀

と

𝑎𝑎

₁

の最大公約数

問題： 問題例： (𝑎𝑎₀, 𝑎𝑎₁) = (28,12), (987654321, 123456789)

計算量の評価法

9

問題例の規模

によって計算量が変わる

⇒問題例の規模に応じた評価

⇒

入力長

𝑛𝑛の関数𝑇𝑇(𝑛𝑛)

として計算量を評価

ただし，入力長および計算量は

計算コストモデル

に依存

定数（一様）コストモデル

すべての数を１語（１単位のデータ）とみなして、どの基本命令も

単位時間で実行できると仮定

対数コストモデル

各々の数は，それを表現するのに必要なビット数の語数が必要

であり、基本命令の実行はビット数に応じた時間がかかると仮定

※ 大きな数字を扱うことが本質的な問題は対数コストモデル、そうでない場合は 定数コストモデルで考えることが多い

「オーダー」記法について

漸近的計算量

11

オーダー評価

とは

計算量

𝑇𝑇(𝑛𝑛)は十分大きな 𝑛𝑛 に対して評価する

定数倍の差はないものとみなす

定義［漸近的上界（

ビッグオー記法

）］

𝑇𝑇(𝑛𝑛) = O(𝑓𝑓(𝑛𝑛)) ⇔ ある実数𝑐𝑐 > 0と自然数𝑛𝑛

₀

が存在して

全ての

𝑛𝑛 ≥ 𝑛𝑛

₀

に対して

𝑇𝑇 𝑛𝑛 ≤ 𝑐𝑐 ⋅ 𝑓𝑓(𝑛𝑛)

が成り立つ

「𝑇𝑇(𝑛𝑛)は，オーダー𝑓𝑓(𝑛𝑛)である」または「𝑇𝑇(𝑛𝑛)は，ビッグオー𝑓𝑓(𝑛𝑛)である」と読む 漸近的上界(asymptotic upper bound)＝意味 「関数𝑇𝑇(𝑛𝑛)は𝑓𝑓(𝑛𝑛)と同じか小さい」 漸近的上界はいくらでも存在するができるだけ単純で精度のよいものがよい

(1) 2𝑛𝑛2 _{+ 5𝑛𝑛 + 1000 = O(𝑛𝑛}2₎ ← best!

(2) 2𝑛𝑛2 _{+ 5𝑛𝑛 + 1000 = O(𝑛𝑛}2 _{+ 𝑛𝑛) ← (1)より複雑}

なぜ計算時間をオーダーで測るのか？

12

オーダーが大きいほど，係数によらず計算時間が急速に増加する

質問： 問題のサイズを大きくしていったらどうなるか？

100𝑛𝑛, 5𝑛𝑛2, 𝑛𝑛3/2, 2𝑛𝑛の計算時間をもつ4つのプログラムに対して， その入力_{𝑛𝑛を増やしながら走らせたときの計算時間のグラフ}

なぜ計算時間をオーダーで測るのか？

13

質問： 時間をかけた分だけ大きなサイズの問題が解けるか？

O(𝑛𝑛)時間アルゴリズムなら計算時間を10倍にすると10倍の

サイズの問題が解ける

しかし，

O(𝑛𝑛

3

)時間なら2.3倍

，

O(2

𝑛𝑛

)時間なら1.3倍

しか

大きくならない！

実行時間 𝑇𝑇(𝑛𝑛) 10 3_{秒で解ける} 最大問題サイズ 10 4_{秒で解ける} 最大問題サイズ 増大率 （倍）

100𝑛𝑛

10

100

10.0

5𝑛𝑛

2

14

45

3.2

𝑛𝑛

3

/2

12

27

2.3

2

𝑛𝑛

10

13

1.3

漸近的計算量の性質

14

𝑇𝑇

1

𝑛𝑛 = O 𝑓𝑓 𝑛𝑛 , 𝑇𝑇

2

𝑛𝑛 = O 𝑔𝑔 𝑛𝑛 のとき，次の等式が成立

1.

_𝑇𝑇

₁

_{(𝑛𝑛) + 𝑇𝑇}

₂

_{(𝑛𝑛) = O max 𝑓𝑓 𝑛𝑛 , 𝑔𝑔 𝑛𝑛}

意味： いくつかの処理を順次行う場合は一番遅い処理が

全体の処理速度を支配する

2.

_𝑇𝑇

₁

_{𝑛𝑛 𝑇𝑇}

₂

_{(𝑛𝑛) = O 𝑓𝑓 𝑛𝑛 𝑔𝑔 𝑛𝑛}

意味： 処理を繰り返し行うとその回数分時間がかかる

オーダー表記の注意点： （左辺の精度）

≥（右辺の精度）

証明してみよう！

（例） ○

2𝑛𝑛

2

+ 5𝑛𝑛 + 1000 = O 𝑛𝑛

2

×

O(𝑛𝑛

2

) = 2𝑛𝑛

2

+ 5𝑛𝑛 + 1000

(例)

𝑛𝑛

2

+ 𝑛𝑛

3

= O 𝑛𝑛

3

,

𝑛𝑛

2

・

𝑛𝑛

3

= O 𝑛𝑛

5

漸近的下界

15

定義［漸近的下界（

ビッグオメガ記法

）］

𝑇𝑇(𝑛𝑛) = Ω(𝑓𝑓(𝑛𝑛)) ⇔ ある実数𝑐𝑐 > 0と自然数𝑛𝑛

₀

が存在して

全ての

𝑛𝑛 ≥ 𝑛𝑛

₀

に対して

𝑇𝑇 𝑛𝑛 ≥ 𝑐𝑐 ⋅ 𝑓𝑓(𝑛𝑛)

が成り立つ

(例) _{𝑇𝑇 𝑛𝑛 = 2𝑛𝑛}2 _{+ 5𝑛𝑛 + 1000 = Ω 𝑛𝑛}2 𝑇𝑇 𝑛𝑛 = �𝑛𝑛_𝑛𝑛32_,, if 𝑛𝑛は奇数_{if 𝑛𝑛は偶数 𝑇𝑇(𝑛𝑛) = Ω 𝑛𝑛}2 漸近的下界の別定義 𝑇𝑇(𝑛𝑛) = Ω(𝑓𝑓(𝑛𝑛)) ⇔ ある実数𝑐𝑐 > 0が存在して，無限個の𝑛𝑛に対して 𝑇𝑇 𝑛𝑛 ≥ 𝑐𝑐 ⋅ 𝑓𝑓(𝑛𝑛)が成り立つ 下の定義では Ω 𝑛𝑛3 次の定義をΩの定義として採用することもある（研究論文ではこちらも多い） 上の定義の方が厳しいので上の定義を満たせば次の定義も満たす

漸近的下界(asymptotic lower bound)=意味 「関数_{𝑇𝑇(𝑛𝑛)は𝑓𝑓(𝑛𝑛)と同じか大きい}」 「_{𝑇𝑇(𝑛𝑛)はビッグオメガ𝑓𝑓(𝑛𝑛)である}」と読む

漸近的にタイトな限界

16

定義［漸近的にタイトな限界（

asymptotic tight bound）］

𝑇𝑇(𝑛𝑛) = Θ(𝑓𝑓(𝑛𝑛)) ⇔ ある実数𝑐𝑐

₀

, 𝑐𝑐

₁

> 0と自然数𝑛𝑛

₀

が存在して

全ての

𝑛𝑛 ≥ 𝑛𝑛

₀

に対して，

𝑐𝑐

0

𝑓𝑓 𝑛𝑛 ≤ 𝑇𝑇 𝑛𝑛 ≤ 𝑐𝑐

1

𝑓𝑓 𝑛𝑛 が成り立つ

𝑇𝑇(𝑛𝑛) = Θ(𝑓𝑓(𝑛𝑛)) ⇔ 𝑇𝑇(𝑛𝑛) = O(𝑓𝑓(𝑛𝑛)), 𝑇𝑇(𝑛𝑛) = Ω(𝑓𝑓(𝑛𝑛)) 一般に Ωの別定義であれば ⇒ のみ成立 「_{𝑇𝑇(𝑛𝑛)はビッグシータ𝑓𝑓(𝑛𝑛)である}」と読む (例) 𝑇𝑇 𝑛𝑛 = 2𝑛𝑛2 + 5𝑛𝑛 + 1000 = Θ 𝑛𝑛2 𝑇𝑇 𝑛𝑛 = �𝑛𝑛2, if 𝑛𝑛は奇数 𝑛𝑛3, if 𝑛𝑛は偶数 𝑇𝑇 𝑛𝑛 ≠ Θ 𝑛𝑛3

（上級編）教養として

oとωも知っておこう！

17 定義［漸近的にタイトでない上界］ 𝑇𝑇(𝑛𝑛) = o(𝑓𝑓(𝑛𝑛)) ⇔ 任意の実数_{𝑐𝑐 > 0に対し，ある自然数𝑛𝑛0}が存在して， 全ての_{𝑛𝑛 ≥ 𝑛𝑛0}に対して _{𝑇𝑇 𝑛𝑛 ≤ 𝑐𝑐 ⋅ 𝑓𝑓 𝑛𝑛 が成り立つ} (例) 2𝑛𝑛 = o 𝑛𝑛2 , 2𝑛𝑛2 ≠ o 𝑛𝑛2 「𝑇𝑇(𝑛𝑛)はスモールオー𝑓𝑓(𝑛𝑛)である」と読む 𝑇𝑇(𝑛𝑛)は𝑛𝑛が無限大に近づくにつれて，𝑓𝑓(𝑛𝑛)に対して相対的に小さくなる すなわち， _lim 𝑛𝑛→∞ T 𝑛𝑛 𝑓𝑓 𝑛𝑛 = 0 となる 𝑇𝑇(𝑛𝑛)は𝑓𝑓(𝑛𝑛)より真に小さい 定義［漸近的にタイトでない下界］ 𝑇𝑇(𝑛𝑛) = 𝜔𝜔(𝑓𝑓(𝑛𝑛)) ⇔ 任意の実数_{𝑐𝑐 > 0に対し，ある自然数𝑛𝑛0}が存在して， 全ての_{𝑛𝑛 ≥ 𝑛𝑛0}に対して _{𝑇𝑇 𝑛𝑛 ≥ 𝑐𝑐 ⋅ 𝑓𝑓 𝑛𝑛 が成り立つ} (例) 2𝑛𝑛2 = 𝜔𝜔 𝑛𝑛 , 2𝑛𝑛2 ≠ 𝜔𝜔 𝑛𝑛2 「𝑇𝑇(𝑛𝑛)はスモールオメガ𝑓𝑓(𝑛𝑛)である」と読む 𝑇𝑇(𝑛𝑛)は𝑛𝑛が無限大に近づくにつれて，𝑓𝑓(𝑛𝑛)に対して相対的に大きくなる すなわち， _lim 𝑛𝑛→∞ T 𝑛𝑛 𝑓𝑓 𝑛𝑛 = ∞ となる 𝑇𝑇(𝑛𝑛)は𝑓𝑓(𝑛𝑛)より真に大きい 𝑇𝑇(𝑛𝑛) = o(𝑓𝑓(𝑥𝑥)) ⇔ 𝑓𝑓(𝑥𝑥) = 𝜔𝜔(𝑇𝑇(𝑛𝑛))

オーダーの計算の基本

規則１： 𝑇𝑇(𝑛𝑛)が𝑛𝑛の多項式ならば，最大次数の項のオーダーになる (例) _2𝑛𝑛2 _{+ 3𝑛𝑛 + 100 = O 𝑛𝑛}2 10𝑛𝑛 + 2 𝑛𝑛 + 5 = 10𝑛𝑛1 + 2𝑛𝑛0.5 + 5 = O 𝑛𝑛 規則２： 次のオーダーの式が成立する log 𝑛𝑛 = O(𝑛𝑛) 𝑛𝑛 = O 2𝑛𝑛 任意の𝑐𝑐 > 0に対して，log 𝑛𝑛 = O 𝑛𝑛𝑐𝑐 規則３： _{𝑇𝑇(𝑛𝑛)が}いくつかの項の和ならば，最大次数の項のオーダーになる 18 (例) _3𝑛𝑛2 _{+ 2 𝑛𝑛 + 100 log 𝑛𝑛 + 5 = O 𝑛𝑛}2

増加のオーダーによる比較

(1)

19

計算時間が

𝑇𝑇

₁

𝑛𝑛 と𝑇𝑇

₂

𝑛𝑛 のアルゴリズムではどちらが速いか？

⇒ 増加のオーダーが小さい方が速い

規則４： 𝑇𝑇₁(𝑛𝑛)よりも𝑇𝑇₂(𝑛𝑛)の方が増加のオーダーが大きい ⇔ _lim 𝑛𝑛→∞ 𝑇𝑇1 𝑛𝑛 𝑇𝑇2 𝑛𝑛 = 0 ⇔ lim𝑛𝑛→∞ 𝑇𝑇2 𝑛𝑛 𝑇𝑇1 𝑛𝑛 = ∞ 規則５： _{𝑇𝑇1(𝑛𝑛)と𝑇𝑇2(𝑛𝑛)は増加のオーダーが等しい} ⇔ 𝑇𝑇₁ 𝑛𝑛 = Θ T₂ 𝑛𝑛 ⇔ 𝑇𝑇₂ 𝑛𝑛 = Θ 𝑇𝑇₁ 𝑛𝑛 𝑇𝑇₁(𝑛𝑛)と𝑇𝑇₂(𝑛𝑛)は増加のオーダーが等しい ⇐_⇏ ある𝑐𝑐 > 0が存在し， lim 𝑛𝑛→∞ 𝑇𝑇1 𝑛𝑛 𝑇𝑇2 𝑛𝑛 = 𝑐𝑐 注意

増加のオーダーによる比較

(2)

20 規則６： ロピタル（de l’Hospital）の法則 1. 𝑓𝑓(𝑥𝑥)と𝑔𝑔(𝑥𝑥)が微分可能で，𝑓𝑓(𝑎𝑎) = 𝑔𝑔(𝑎𝑎) = 0かつ𝑥𝑥 = 𝑎𝑎以外で𝑔𝑔′ _{𝑥𝑥 ≠ 0} であるなら，lim 𝑥𝑥→𝑎𝑎 𝑓𝑓 𝑥𝑥 𝑔𝑔 𝑥𝑥 = lim_{𝑥𝑥→𝑎𝑎} 𝑓𝑓′ 𝑥𝑥 𝑔𝑔′ 𝑥𝑥 が成り立つ 2. 𝑓𝑓(𝑥𝑥)と𝑔𝑔(𝑥𝑥)が微分可能で， lim_{𝑥𝑥→∞}𝑓𝑓(𝑥𝑥) = lim_{𝑥𝑥→∞}𝑔𝑔(𝑥𝑥) = ∞ であれば， lim 𝑥𝑥→∞ 𝑓𝑓 𝑥𝑥 𝑔𝑔 𝑥𝑥 = lim_{𝑥𝑥→∞} 𝑓𝑓′ 𝑥𝑥 𝑔𝑔′ _𝑥𝑥 が成り立つ （例） _𝑛𝑛0.01と _{log 𝑛𝑛} 100ではどちらが漸近的に増加率が大きいか？ lim 𝑛𝑛→∞ log 𝑛𝑛 100 𝑛𝑛0.01 = lim_{𝑛𝑛→∞}100 log 𝑛𝑛 99 _{× 1/𝑛𝑛} 0.01𝑛𝑛−0.99 = lim_{𝑛𝑛→∞}100 log 𝑛𝑛 99 0.01𝑛𝑛0.01

発展問題

21

次のオーダー表記を簡略化せよ

(a)

_{O 𝑛𝑛 log 𝑛𝑛 + 𝑛𝑛}

2

_{+ O 𝑛𝑛}

1.83

_{log 𝑛𝑛}

明らかに_{𝑛𝑛 log 𝑛𝑛 < 𝑛𝑛}2, 𝑛𝑛 log 𝑛𝑛 < 𝑛𝑛1.83 _{log 𝑛𝑛である．また，} lim

𝑛𝑛→∞

𝑛𝑛1.83 log 𝑛𝑛

𝑛𝑛2 = lim_{𝑛𝑛→∞}log 𝑛𝑛_𝑛𝑛0.17 = lim_{𝑛𝑛→∞0.17𝑛𝑛}1/𝑛𝑛−0.83 = lim_{𝑛𝑛→∞ 0.17𝑛𝑛}1 0.17 = 0.

よって，十分大きな_{𝑛𝑛に対して𝑛𝑛}1.83 _{log 𝑛𝑛 < 𝑛𝑛}2であるから O 𝑛𝑛 log 𝑛𝑛 + 𝑛𝑛2 + O 𝑛𝑛1.83 log 𝑛𝑛 = O 𝑛𝑛2 となる．

(b)

_{O 𝑛𝑛}

log 𝑛𝑛

_{+ 𝑛𝑛}

100

_{+ 𝑛𝑛}

30

_{log 𝑛𝑛}

𝑛𝑛30 log 𝑛𝑛 < 𝑛𝑛100 は明らか．

また十分大きな_{𝑛𝑛に対して，𝑛𝑛}100 _{< 𝑛𝑛}log 𝑛𝑛 が成り立つ．よって， O 𝑛𝑛log 𝑛𝑛 + 𝑛𝑛100 + 𝑛𝑛30 log 𝑛𝑛 = O 𝑛𝑛log 𝑛𝑛 となる．

アルゴリズムの計算量

計算量を問題例の入力長

𝑛𝑛 の関数としてオーダー評価したもの

以下の二つの評価法がある。

（例） 入力長がNの問題例に対し確率(𝑛𝑛 − 1)/𝑛𝑛でO 𝑛𝑛 ， 確率_{1/𝑛𝑛でO 𝑛𝑛}2 であるようなアルゴリズムの計算量 ⇒ 最悪時間計算量 O 𝑛𝑛2 平均時間計算量 _{O 𝑛𝑛}

最悪計算量

（

worst case complexity）

入力長が

𝑛𝑛 である問題例の中で最大の計算量

平均計算量

（

average case complexity）

入力長が

𝑛𝑛 である問題例の計算量の期待値

※ 通常は，最悪計算量で評価することが多い

𝑤𝑤₃ 𝑤𝑤₄ 𝑤𝑤₁ 時間 𝑤𝑤₂

お風呂に入る順番を決めよう！

全員の

待ち時間

と

入浴時間

の合計を最小にする順番を求める

23

お風呂スケジューリング問題の計算量は？

𝑛𝑛人のお風呂スケジューリング問題の

解の空間は

𝑛𝑛! （順列通り）

もある！

単純な方法だと

O 𝑛𝑛! 時間かかるが…

うまくやれば

O 𝑛𝑛 log 𝑛𝑛

時間で解ける！

今日のまとめ

アルゴリズムの計算量とは？

時間計算量と領域計算量

入力長

𝑛𝑛の関数𝑇𝑇(𝑛𝑛)として計算量を評価

オーダー記法

漸近的計算量（十分大きな

𝑛𝑛で．定数倍は無視）

ビッグオー(

O)，ビッグオメガ(Ω)，ビッグシータ(Θ)，

スモールオー（

o），スモールオメガ（𝜔𝜔）

オーダーの比較の仕方，簡略化の方法

最悪計算量と平均計算量

24