計算量けいさんりょうの基本きほん

1導入どうにゅう

この講義こうぎでは、入力にゅうりょくの規模きぼに応おうじた実行時間じっこうじかんと記憶領域きおくりょういきの増加ぞうかを評価ひょうかする方法ほうほうを説明せつめいする。特定とくていの計算機けいさんきで計測けいそくした秒数びょうすうだけでなく、入力にゅうりょくが大規模だいきぼになったときの増加率ぞうかりつを比較ひかくすることで、アルゴリズムの性質せいしつを分析ぶんせきできる。

2入力にゅうりょくサイズと計算資源けいさんしげん

入力にゅうりょくサイズInput size $$n$$n とは、問題もんだいの入力規模にゅうりょくきぼを表あらわす非負整数ひふせいすうである。一次元配列いちじげんはいれつでは要素数ようそすう、二次元配列にじげんはいれつでは行数ぎょうすうと列数れつすうの組くみ合あわせなど、問題もんだいに適てきした尺度しゃくどを選択せんたくする。したがって、すべての入力にゅうりょくを単一たんいつの $$n$$n で表現ひょうげんできるとは限かぎらない。

時間計算量じかんけいさんりょうTime complexityとは、入力にゅうりょくサイズに対たいして基本操作きほんそうさの実行回数じっこうかいすうがどのように増加ぞうかするかを表あらわす関数かんすうである。空間計算量くうかんけいさんりょうSpace complexityとは、実行中じっこうちゅうに必要ひつような記憶領域きおくりょういきの増加ぞうかを表あらわす関数かんすうである。入力自体にゅうりょくじたいを除外じょがいした追加領域ついかりょういきだけを評価ひょうかする場合ばあいは、補助空間計算量ほじょくうかんけいさんりょうAuxiliary-space complexityと呼よぶ。

3入力にゅうりょくごとの差異さい

同一どういつのサイズ $$n$$n でも、入力内容にゅうりょくないようによって実行回数じっこうかいすうが異ことなることがある。

• 最良計算量さいりょうけいさんりょうBest-case complexityは、サイズ $$n$$n の入力にゅうりょくにおける最小さいしょうの資源使用量しげんしようりょうである。
• 最悪計算量さいあくけいさんりょうWorst-case complexityは、サイズ $$n$$n の入力にゅうりょくにおける最大さいだいの資源使用量しげんしようりょうである。
• 平均計算量へいきんけいさんりょうAverage-case complexityは、サイズ $$n$$n の入力集合にゅうりょくしゅうごうに確率分布かくりつぶんぷを指定していしたときの資源使用量しげんしようりょうの期待値きたいちである。

平均計算量へいきんけいさんりょうは確率分布かくりつぶんぷを明示めいじしなければ定義ていぎできない。また、最良さいりょう・平均へいきん・最悪さいあくという入力にゅうりょくの区分くぶんと、次節じせつの $$O$$O・$$\mathrm{\Theta }$$\Theta・$$\mathrm{\Omega }$$\Omega という関数かんすうの漸近的関係ぜんきんてきかんけいは別べつの概念がいねんである。

4漸近記法ぜんきんきほう

$$f\left(n\right)$$f(n) と $$g\left(n\right)$$g(n) を十分じゅうぶん大おおきな $$n$$n で非負ひふとなる関数かんすうとする。

• $$f\left(n\right)=O\left(g\right(n\left)\right)$$f(n)=O(g(n)) とは、ある正せいの定数ていすう $$c,n_0$$c,n_0 が存在そんざいし、すべての $$n\text{[PARSE ERROR: Undefined("Command("ge")")]}{n}_0$$n\ge n_0 で $$f\left(n\right)\text{[PARSE ERROR: Undefined("Command("le")")]}cg\left(n\right)$$f(n)\le c g(n) が成立せいりつすることである。これは漸近的上界ぜんきんてきじょうかいを表あらわす。
• $$f\left(n\right)=\mathrm{\Omega }\left(g\right(n\left)\right)$$f(n)=\Omega(g(n)) とは、ある正せいの定数ていすう $$c,n_0$$c,n_0 が存在そんざいし、すべての $$n\text{[PARSE ERROR: Undefined("Command("ge")")]}{n}_0$$n\ge n_0 で $$cg\left(n\right)\text{[PARSE ERROR: Undefined("Command("le")")]}f\left(n\right)$$c g(n)\le f(n) が成立せいりつすることである。これは漸近的下界ぜんきんてきげかいを表あらわす。
• $$f\left(n\right)=\mathrm{\Theta }\left(g\right(n\left)\right)$$f(n)=\Theta(g(n)) とは、$$f\left(n\right)=O\left(g\right(n\left)\right)$$f(n)=O(g(n)) と $$f\left(n\right)=\mathrm{\Omega }\left(g\right(n\left)\right)$$f(n)=\Omega(g(n)) の双方そうほうが成立せいりつすることである。これは定数倍ていすうばいを除のぞいて漸近的増加率ぜんきんてきぞうかりつが一致いっちすることを表あらわす。

したがって、$$O$$O は上界じょうかいであり、常つねに増加率ぞうかりつの一致いっちを意味いみするわけではない。たとえば $$3n+5=O\left(n^2\right)$$3n+5=O(n^2) も正ただしいが、より精密せいみつな評価ひょうかは $$3n+5=\mathrm{\Theta }\left(n\right)$$3n+5=\Theta(n) である。

5具体例ぐたいれい

$$T\left(n\right)=3n+5$$T(n)=3n+5 とする。$$n\text{[PARSE ERROR: Undefined("Command("ge")")]}1$$n\ge 1 では

が成立せいりつするため、$$T\left(n\right)=\mathrm{\Theta }\left(n\right)$$T(n)=\Theta(n) である。定数項ていすうこうと定数倍ていすうばいは漸近的増加率ぜんきんてきぞうかりつを変更へんこうしない。

長ながさ $$n$$n の配列はいれつを先頭せんとうから検査けんさする線形探索せんけいたんさくでは、先頭せんとうで一致いっちする最良時間さいりょうじかんは $$\mathrm{\Theta }\left(1\right)$$\Theta(1)、末尾まつびで一致いっちするか不一致ふいっちとなる最悪時間さいあくじかんは $$\mathrm{\Theta }\left(n\right)$$\Theta(n) である。一方いっぽう、整列済せいれつずみ配列はいれつの二分探索にぶんたんさくは、各比較かくひかくで候補区間こうほくかんを半分はんぶんに縮小しゅくしょうする。$$k$$k 回後かいごの候補数こうほすうは高々たかだか $$n/2^k$$n/2^k であるため、空配列くうはいれつも含ふくめた最悪時間さいあくじかんは $$\mathrm{\Theta }\left(\log \right(n+1\left)\right)$$\Theta(\log(n+1)) となる。

入力にゅうりょくを参照さんしょうするだけで一定個数いっていこすうの変数へんすうを使用しようするアルゴリズムの補助空間ほじょくうかんは $$\mathrm{\Theta }\left(1\right)$$\Theta(1) である。長ながさ $$n$$n の別配列べつはいれつを確保かくほするなら、補助空間ほじょくうかんは $$\mathrm{\Theta }\left(n\right)$$\Theta(n) となる。時間じかんと空間くうかんは独立どくりつに評価ひょうかする。

6後続講義こうぞくこうぎへの接続せつぞく

次つぎの再帰講義さいきこうぎでは、再帰呼出さいきよびだしの回数かいすうと最大深度さいだいしんどから時間じかん・補助空間計算量ほじょくうかんけいさんりょうを導出どうしゅつする。その後あとの整列講義せいれつこうぎと探索講義たんさくこうぎでは、適用条件てきようじょうけん、正当性せいとうせい、計算量けいさんりょうを併あわせて比較ひかくする。

7要約ようやく

• 入力にゅうりょくサイズは、問題もんだいに適てきした尺度しゃくどによって定義ていぎする。
• 時間計算量じかんけいさんりょうと空間計算量くうかんけいさんりょうは、異ことなる計算資源けいさんしげんを評価ひょうかする。
• 最良さいりょう・平均へいきん・最悪さいあくは入力にゅうりょくの区分くぶんであり、$$O$$O・$$\mathrm{\Theta }$$\Theta・$$\mathrm{\Omega }$$\Omega は関数間かんすうかんの漸近的関係ぜんきんてきかんけいである。
• $$O$$O は上界じょうかい、$$\mathrm{\Omega }$$\Omega は下界げかい、$$\mathrm{\Theta }$$\Theta は同一どういつの関数かんすうによる上界じょうかいと下界げかいを表あらわす。