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

(1)

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

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

大学院情報科学研究院情報理工学部門情報知識ネットワーク研究室

喜田拓也

2019/5/21 講義資料

(2)

今日の内容

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

漸近的計算量

オーダーの計算の方法

最悪計算量と平均計算量ポイント

オーダー記法

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

2

(3)

𝑤𝑤₃ 𝑤𝑤₄

𝑤𝑤₁

時間

𝑤𝑤₂

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

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

全員の待ち時間と入浴時間の合計を最小にする順番を求める

3

(4)

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

待ち時間入浴時間

𝑤𝑤 ₁ + 3𝑤𝑤 ₂ + 4𝑤𝑤 ₃ + 2𝑤𝑤 ₄

0 𝑤𝑤 ₃

𝑤𝑤 ₃ + 𝑤𝑤 ₂ 𝑤𝑤 ₄

𝑤𝑤 ₃ 𝑤𝑤 ₂

𝑤𝑤 ₃ + 𝑤𝑤 ₂ + 𝑤𝑤 ₄ 𝑤𝑤 ₁

𝑤𝑤₃

𝑤𝑤₄ 𝑤𝑤₂

𝑤𝑤₁

4

例えば，こんな順番だと …

もっと小さくできます

(5)

𝑤𝑤₁

時間

𝑤𝑤₂

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

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

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

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

私も！

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

5

(6)

よいアルゴリズムとは？

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

計算時間

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

外部記憶への入出力数ネットワークの通信量

ほかの要素

再利用可能性 (Reusability) 読みやすさ (Readability) 移植しやすさ (Portability) etc...

6

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

(7)

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

7

時間計算量 (time complexity) ⇒ 計算のステップ数領域計算量 (space complexity) ⇒ 記憶領域量

ある問題を解くために必要な計算量を測りたい・・・でも計算時間やメモリサイズはいろいろな要素に依存する！

1. アルゴリズムの方式 2. コーディングスタイル

3. 言語の種類とコンパイラの質 4. ハードウェアの性能

5. 入力そのもの

(8)

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

8

問題例１解１

問題例２解２

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

アルゴリズム

最大公約数を求める問題 (GCD) 入力：正整数 𝑎𝑎 ₀ , 𝑎𝑎 ₁

出力： 𝑎𝑎 ₀ と 𝑎𝑎 ₁ の最大公約数

問題：

問題例： (𝑎𝑎

₀

, 𝑎𝑎

₁

) = (28,12) , (987654321, 123456789)

^{かかる時間}_は異なる

(9)

計算量の評価法

9

問題例の規模によって計算量が変わる

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

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

ただし，入力長および計算量は計算コストモデルに依存定数（一様）コストモデル

すべての数を１語（１単位のデータ）とみなして、どの基本命令も単位時間で実行できると仮定

対数コストモデル

各々の数は，それを表現するのに必要なビット数の語数が必要であり、基本命令の実行はビット数に応じた時間がかかると仮定

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

(10)

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

ビッグオーダーとかグランドオーダーとか？

||￣￣￣￣￣￣￣￣￣￣￣||

|| 位数とか次数｡ ∧_∧ いいですね。

|| って意味です＼ (ﾟДﾟ,,)

||＿＿＿＿＿＿＿＿＿⊂⊂ |

(11)

漸近的計算量

11

オーダー評価とは

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

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

定義［漸近的上界（ビッグオー記法）］

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

₀

が存在して全ての 𝑛𝑛 ≥ 𝑛𝑛

₀

に対して 𝑇𝑇 𝑛𝑛 ≤ 𝑐𝑐 ⋅ 𝑓𝑓(𝑛𝑛) が成り立つ

「 𝑇𝑇(𝑛𝑛) は，オーダー 𝑓𝑓(𝑛𝑛) である」または「 𝑇𝑇(𝑛𝑛) は，ビッグオー 𝑓𝑓(𝑛𝑛) である」と読む

漸近的上界 (asymptotic upper bound) ＝意味「関数 𝑇𝑇 ( 𝑛𝑛 ) は 𝑓𝑓 ( 𝑛𝑛 ) と同じか小さい」

漸近的上界はいくらでも存在するができるだけ単純で精度のよいものがよい (1) 2𝑛𝑛

²

+ 5𝑛𝑛 + 1000 = O(𝑛𝑛

²

) ← best!

(2) 2𝑛𝑛

²

+ 5𝑛𝑛 + 1000 = O(𝑛𝑛

²

+ 𝑛𝑛) ← (1) より複雑

(3) 2𝑛𝑛

²

+ 5𝑛𝑛 + 1000 = O(𝑛𝑛

³

) ← (1) より精度が悪い

(12)

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

12

オーダーが大きいほど，係数によらず計算時間が急速に増加する質問：問題のサイズを大きくしていったらどうなるか？

100𝑛𝑛, 5𝑛𝑛², 𝑛𝑛³/2, 2^𝑛𝑛の計算時間をもつ4つのプログラムに対して，

その入力𝑛𝑛を増やしながら走らせたときの計算時間のグラフ

(13)

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

13

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

O(𝑛𝑛) 時間アルゴリズムなら計算時間を 10 倍にすると 10 倍のサイズの問題が解ける

しかし， O(𝑛𝑛

³

) 時間なら 2.3 倍， O(2

^𝑛𝑛

) 時間なら 1.3 倍しか大きくならない！

実行時間

𝑇𝑇(𝑛𝑛) 10

³

秒で解ける

最大問題サイズ 10

⁴

秒で解ける最大問題サイズ

増大率

（倍）

100𝑛𝑛 10 100 10.0

5𝑛𝑛

²

14 45 3.2

𝑛𝑛

³

/2 12 27 2.3

2

^𝑛𝑛

10 13 1.3

(14)

漸近的計算量の性質

14

𝑇𝑇

₁

𝑛𝑛 = O 𝑓𝑓 𝑛𝑛 , 𝑇𝑇

₂

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

1. 𝑇𝑇

₁

(𝑛𝑛) + 𝑇𝑇

₂

(𝑛𝑛) = O max 𝑓𝑓 𝑛𝑛 , 𝑔𝑔 𝑛𝑛

意味：いくつかの処理を順次行う場合は一番遅い処理が全体の処理速度を支配する

2. 𝑇𝑇

₁

𝑛𝑛 𝑇𝑇

₂

(𝑛𝑛) = O 𝑓𝑓 𝑛𝑛 𝑔𝑔 𝑛𝑛

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

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

証明してみよう！

（例） ○ 2𝑛𝑛

²

+ 5𝑛𝑛 + 1000 = O 𝑛𝑛

²

× O(𝑛𝑛

²

) = 2𝑛𝑛

²

+ 5𝑛𝑛 + 1000

(例) 𝑛𝑛

²

+ 𝑛𝑛

³

= O 𝑛𝑛

³

, 𝑛𝑛

²

・ 𝑛𝑛

³

= O 𝑛𝑛

⁵

(15)

漸近的下界

15

定義［漸近的下界（ビッグオメガ記法）］

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

₀

が存在して全ての 𝑛𝑛 ≥ 𝑛𝑛

₀

に対して 𝑇𝑇 𝑛𝑛 ≥ 𝑐𝑐 ⋅ 𝑓𝑓(𝑛𝑛) が成り立つ

(例) 𝑇𝑇 𝑛𝑛 = 2𝑛𝑛

²

+ 5𝑛𝑛 + 1000 = Ω 𝑛𝑛

²

𝑇𝑇 𝑛𝑛 = �𝑛𝑛

²

, if 𝑛𝑛 は奇数

𝑛𝑛

³

, if 𝑛𝑛 は偶数 𝑇𝑇(𝑛𝑛) = Ω 𝑛𝑛

²

漸近的下界の別定義

𝑇𝑇(𝑛𝑛) = Ω(𝑓𝑓(𝑛𝑛)) ⇔ ある実数 𝑐𝑐 > 0 が存在して，無限個の 𝑛𝑛 に対して

𝑇𝑇 𝑛𝑛 ≥ 𝑐𝑐 ⋅ 𝑓𝑓(𝑛𝑛) が成り立つ

下の定義では Ω 𝑛𝑛

³

次の定義を Ω の定義として採用することもある（研究論文ではこちらも多い）

上の定義の方が厳しいので上の定義を満たせば次の定義も満たす

漸近的下界 (asymptotic lower bound)= 意味「関数 𝑇𝑇(𝑛𝑛) は 𝑓𝑓(𝑛𝑛) と同じか大きい」

「 𝑇𝑇(𝑛𝑛) はビッグオメガ 𝑓𝑓(𝑛𝑛) である」と読む

(16)

漸近的にタイトな限界

16

定義［漸近的にタイトな限界（ asymptotic tight bound ）］

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

₀

, 𝑐𝑐

₁

> 0 と自然数 𝑛𝑛

₀

が存在して

全ての 𝑛𝑛 ≥ 𝑛𝑛

₀

に対して，

𝑐𝑐

₀

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

₁

𝑓𝑓 𝑛𝑛 が成り立つ

𝑇𝑇(𝑛𝑛) = Θ(𝑓𝑓(𝑛𝑛)) ⇔ 𝑇𝑇(𝑛𝑛) = O(𝑓𝑓(𝑛𝑛)) , 𝑇𝑇(𝑛𝑛) = Ω(𝑓𝑓(𝑛𝑛)) 一般に

Ω の別定義であれば ⇒ のみ成立

「 𝑇𝑇(𝑛𝑛) はビッグシータ 𝑓𝑓(𝑛𝑛) である」と読む

(例) 𝑇𝑇 𝑛𝑛 = 2𝑛𝑛

²

+ 5𝑛𝑛 + 1000 = Θ 𝑛𝑛

²

𝑇𝑇 𝑛𝑛 = �𝑛𝑛

²

, if 𝑛𝑛 は奇数

𝑛𝑛

³

, if 𝑛𝑛 は偶数 𝑇𝑇 𝑛𝑛 ≠ Θ 𝑛𝑛

³

(17)

（上級編）教養として o と ω も知っておこう！

17

定義［漸近的にタイトでない上界］

𝑇𝑇(𝑛𝑛) = o(𝑓𝑓(𝑛𝑛)) ⇔ 任意の実数 𝑐𝑐 > 0 に対し，ある自然数 𝑛𝑛

₀

が存在して，

全ての 𝑛𝑛 ≥ 𝑛𝑛

₀

に対して 𝑇𝑇 𝑛𝑛 ≤ 𝑐𝑐 ⋅ 𝑓𝑓 𝑛𝑛 が成り立つ

(例) 2𝑛𝑛 = o 𝑛𝑛

²

, 2𝑛𝑛

²

≠ o 𝑛𝑛

²

「 𝑇𝑇(𝑛𝑛) はスモールオー 𝑓𝑓(𝑛𝑛) である」と読む

𝑇𝑇(𝑛𝑛) は 𝑛𝑛 が無限大に近づくにつれて， 𝑓𝑓(𝑛𝑛) に対して相対的に小さくなる

すなわち，

_{𝑛𝑛→∞}

lim

^{T 𝑛𝑛}_{𝑓𝑓 𝑛𝑛}

= 0 となる

_{𝑇𝑇(𝑛𝑛)}_は_{𝑓𝑓(𝑛𝑛)}_{より真に小さい}

定義［漸近的にタイトでない下界］

𝑇𝑇(𝑛𝑛) = 𝜔𝜔(𝑓𝑓(𝑛𝑛)) ⇔ 任意の実数 𝑐𝑐 > 0 に対し，ある自然数 𝑛𝑛

₀

が存在して，

全ての 𝑛𝑛 ≥ 𝑛𝑛

₀

に対して 𝑇𝑇 𝑛𝑛 ≥ 𝑐𝑐 ⋅ 𝑓𝑓 𝑛𝑛 が成り立つ

(例) 2𝑛𝑛

²

= 𝜔𝜔 𝑛𝑛 , 2𝑛𝑛

²

≠ 𝜔𝜔 𝑛𝑛

²

「 𝑇𝑇(𝑛𝑛) はスモールオメガ 𝑓𝑓(𝑛𝑛) である」と読む

𝑇𝑇(𝑛𝑛) は 𝑛𝑛 が無限大に近づくにつれて， 𝑓𝑓(𝑛𝑛) に対して相対的に大きくなる

すなわち，

_{𝑛𝑛→∞}

lim

^{T 𝑛𝑛}_{𝑓𝑓 𝑛𝑛}

= ∞ となる

_{𝑇𝑇(𝑛𝑛)}_は_{𝑓𝑓(𝑛𝑛)}_{より真に大きい}

𝑇𝑇(𝑛𝑛) = o(𝑓𝑓(𝑥𝑥))⇔ 𝑓𝑓(𝑥𝑥) = 𝜔𝜔(𝑇𝑇(𝑛𝑛))

(18)

オーダーの計算の基本

規則１： 𝑇𝑇(𝑛𝑛) が 𝑛𝑛 の多項式ならば，最大次数の項のオーダーになる

(例) 2𝑛𝑛

²

+ 3𝑛𝑛 + 100 = O 𝑛𝑛

²

10𝑛𝑛 + 2 𝑛𝑛 + 5 = 10𝑛𝑛

¹

+ 2𝑛𝑛

^0.5

+ 5 = O 𝑛𝑛 規則２：次のオーダーの式が成立する

log 𝑛𝑛 = O(𝑛𝑛) 𝑛𝑛 = O 2

^𝑛𝑛

任意の 𝑐𝑐 > 0 に対して， log 𝑛𝑛 = O 𝑛𝑛

^𝑐𝑐

規則３： 𝑇𝑇(𝑛𝑛) がいくつかの項の和ならば，最大次数の項のオーダーになる

18

(例) 3𝑛𝑛

²

+ 2 𝑛𝑛 + 100 log 𝑛𝑛 + 5 = O 𝑛𝑛

²

(19)

増加のオーダーによる比較 (1)

19

計算時間が 𝑇𝑇

₁

𝑛𝑛 と 𝑇𝑇

₂

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

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

規則４： 𝑇𝑇

₁

(𝑛𝑛) よりも 𝑇𝑇

₂

(𝑛𝑛) の方が増加のオーダーが大きい

⇔

_{𝑛𝑛→∞}

lim

^𝑇𝑇_𝑇𝑇¹ ^𝑛𝑛

2 𝑛𝑛

= 0 ⇔

_{𝑛𝑛→∞}

lim

^𝑇𝑇_𝑇𝑇² ^𝑛𝑛

1 𝑛𝑛

= ∞

規則５： 𝑇𝑇

₁

(𝑛𝑛) と 𝑇𝑇

₂

(𝑛𝑛) は増加のオーダーが等しい

⇔ 𝑇𝑇

₁

𝑛𝑛 = Θ T

₂

𝑛𝑛 ⇔ 𝑇𝑇

₂

𝑛𝑛 = Θ 𝑇𝑇

₁

𝑛𝑛

𝑇𝑇

₁

(𝑛𝑛) と 𝑇𝑇

₂

(𝑛𝑛) は増加のオーダーが等しい ⇐

⇏ ある 𝑐𝑐 > 0 が存在し，

_{𝑛𝑛→∞}

lim

^𝑇𝑇_𝑇𝑇¹ ^𝑛𝑛

2 𝑛𝑛

= 𝑐𝑐

注意

(20)

増加のオーダーによる比較 (2)

20

規則６：ロピタル（ de l’Hospital ）の法則

1. 𝑓𝑓(𝑥𝑥) と 𝑔𝑔(𝑥𝑥) が微分可能で， 𝑓𝑓(𝑎𝑎) = 𝑔𝑔(𝑎𝑎) = 0 かつ 𝑥𝑥 = 𝑎𝑎 以外で 𝑔𝑔

^′

𝑥𝑥 ≠ 0 であるなら，

_{𝑥𝑥→𝑎𝑎}

lim

_{𝑔𝑔 𝑥𝑥}^{𝑓𝑓 𝑥𝑥}

= lim

_{𝑥𝑥→𝑎𝑎}_𝑔𝑔^𝑓𝑓^′_′ ^𝑥𝑥_𝑥𝑥

が成り立つ

2. 𝑓𝑓(𝑥𝑥) と 𝑔𝑔(𝑥𝑥) が微分可能で，

_{𝑥𝑥→∞}

lim 𝑓𝑓(𝑥𝑥) = lim

_{𝑥𝑥→∞}

𝑔𝑔(𝑥𝑥) = ∞ であれば，

𝑥𝑥→∞

lim

𝑓𝑓 𝑥𝑥

𝑔𝑔 𝑥𝑥

= lim

_{𝑥𝑥→∞}^𝑓𝑓_𝑔𝑔^′_′ ^𝑥𝑥_𝑥𝑥

が成り立つ

（例） 𝑛𝑛

^0.01

と log 𝑛𝑛

¹⁰⁰

ではどちらが漸近的に増加率が大きいか？

𝑛𝑛→∞

lim

log 𝑛𝑛

¹⁰⁰

𝑛𝑛

^0.01

= lim

_{𝑛𝑛→∞}

100 log 𝑛𝑛

⁹⁹

× 1/𝑛𝑛

0.01𝑛𝑛

^−0.99

= lim

_{𝑛𝑛→∞}

100 log 𝑛𝑛

⁹⁹

0.01𝑛𝑛

^0.01

= lim

_{𝑛𝑛→∞}

100 ⋅ 99 log 𝑛𝑛

⁹⁸

0.01

²

𝑛𝑛

^0.01

= ⋯ = lim

_{𝑛𝑛→∞}

100!

0.01

¹⁰⁰

𝑛𝑛

^0.01

= 0

(21)

発展問題

21

次のオーダー表記を簡略化せよ (a) O 𝑛𝑛 log 𝑛𝑛 + 𝑛𝑛

²

+ O 𝑛𝑛

^1.83

log 𝑛𝑛

明らかに 𝑛𝑛 log 𝑛𝑛 < 𝑛𝑛

²

, 𝑛𝑛 log 𝑛𝑛 < 𝑛𝑛

^1.83

log 𝑛𝑛 である．また，

𝑛𝑛→∞

lim

𝑛𝑛

^1.83

log 𝑛𝑛

𝑛𝑛

²

= lim

_{𝑛𝑛→∞}

log 𝑛𝑛

𝑛𝑛

^0.17

= lim

_{𝑛𝑛→∞}

1/𝑛𝑛

0.17𝑛𝑛

^−0.83

= lim

_{𝑛𝑛→∞}

1 0.17𝑛𝑛

^0.17

= 0.

よって，十分大きな 𝑛𝑛 に対して 𝑛𝑛

^1.83

log 𝑛𝑛 < 𝑛𝑛

²

であるから O 𝑛𝑛 log 𝑛𝑛 + 𝑛𝑛

²

+ O 𝑛𝑛

^1.83

log 𝑛𝑛 = O 𝑛𝑛

²

となる．

(b) O 𝑛𝑛

^{log 𝑛𝑛}

+ 𝑛𝑛

¹⁰⁰

+ 𝑛𝑛

³⁰

log 𝑛𝑛

𝑛𝑛

³⁰

log 𝑛𝑛 < 𝑛𝑛

¹⁰⁰

は明らか．

また十分大きな 𝑛𝑛 に対して， 𝑛𝑛

¹⁰⁰

< 𝑛𝑛

^{log 𝑛𝑛}

が成り立つ．よって，

O 𝑛𝑛

^{log 𝑛𝑛}

+ 𝑛𝑛

¹⁰⁰

+ 𝑛𝑛

³⁰

log 𝑛𝑛 = O 𝑛𝑛

^{log 𝑛𝑛}

となる．

(c) O(𝑛𝑛

³

sin

²

𝑛𝑛)O(2

^𝑛𝑛

/ log 𝑛𝑛)

^{チャレンジ！}

(22)

アルゴリズムの計算量

計算量を問題例の入力長 𝑛𝑛 の関数としてオーダー評価したもの以下の二つの評価法がある。

（例）入力長が 𝑛𝑛 の問題例に対し確率 (𝑛𝑛 − 1)/𝑛𝑛 で O 𝑛𝑛 ，確率 1/𝑛𝑛 で O 𝑛𝑛

²

であるようなアルゴリズムの計算量

⇒ 最悪時間計算量 O 𝑛𝑛

²

平均時間計算量 O 𝑛𝑛

最悪計算量（ worst case complexity ）

入力長が 𝑛𝑛 である問題例の中で最大の計算量平均計算量（ average case complexity ）

入力長が 𝑛𝑛 である問題例の計算量の期待値

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

22

(23)

𝑤𝑤₁

時間

𝑤𝑤₂

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

全員の待ち時間と入浴時間の合計を最小にする順番を求める

23

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

𝑛𝑛 人のお風呂スケジューリング問題の解の空間は 𝑛𝑛! （順列通り）もある！

単純な方法だと O 𝑛𝑛! 時間かかるが …

他に制約がない場合，うまくやれば O 𝑛𝑛 log 𝑛𝑛 時間

で解ける！

(24)

今日のまとめ

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

時間計算量と領域計算量

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

オーダー記法

漸近的計算量（十分大きな 𝑛𝑛 で．定数倍は無視）

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

スモールオー（ o ），スモールオメガ（ 𝜔𝜔 ）オーダーの比較の仕方，簡略化の方法

最悪計算量と平均計算量

24

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