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

date2026-07-14document_iddoc_4f15851d03885718cae9cc76d1608a96description入力サイズに対する時間・空間計算量と、O・Theta・Omega記法の相違を日英両言語で説明する。prerequisitesfor 文の反復 / 対数の基本 / 一次式と二次式type講義statusactive

algorithmfoundationundergraduatelecture

1導入どうにゅう

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

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

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

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

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

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

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

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

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

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

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

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

5具体例ぐたいれい

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

3 n [PARSE ERROR: Undefined("Command(\"le\")")] T (n) [PARSE ERROR: Undefined("Command(\"le\")")] 8 n

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

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

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

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

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

data/lecture/information/algorithm/foundation/recursion-basics.lecture.n.md

7要約ようやく

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

Fundamentals of Computational Complexity

1Introduction

This lecture explains how to evaluate growth in running time and memory use as the input size increases. Rather than relying only on elapsed seconds measured on a particular computer, asymptotic growth permits analysis of an algorithm as inputs become large.

2Input Size and Computational Resources

The {input size} $n$ is a nonnegative integer that measures the scale of a problem instance. An appropriate measure depends on the problem: a one-dimensional array may use its number of elements, whereas a two-dimensional array may require both its numbers of rows and columns. Not every input is therefore adequately described by a single parameter.

{Time complexity} is a function describing how the number of executed basic operations grows with input size. {Space complexity} is a function describing growth in memory required during execution. When the analysis excludes storage occupied by the input itself and counts only additional storage, the measure is called {auxiliary-space complexity}.

3Variation among Inputs

Inputs of the same size can require different amounts of a resource.

{Best-case complexity} is the minimum resource use among inputs of size $n$ .
{Worst-case complexity} is the maximum resource use among inputs of size $n$ .
{Average-case complexity} is the expected resource use under a specified probability distribution on inputs of size $n$ .

Average-case complexity is undefined until the probability distribution is specified. Moreover, best, average, and worst cases classify inputs, whereas $O$ , $Θ$ , and $Ω$ describe asymptotic relations between functions. These are separate concepts.

4Asymptotic Notation

Let $f (n)$ and $g (n)$ be nonnegative for all sufficiently large $n$ .

$f (n) = O (g (n))$ means that positive constants $c, n_{0}$ exist such that $f (n) [PARSE ERROR: Undefined("Command(\"le\")")] c g (n)$ for every $n [PARSE ERROR: Undefined("Command(\"ge\")")] n_{0}$ . It states an asymptotic upper bound.
$f (n) = Ω (g (n))$ means that positive constants $c, n_{0}$ exist such that $c g (n) [PARSE ERROR: Undefined("Command(\"le\")")] f (n)$ for every $n [PARSE ERROR: Undefined("Command(\"ge\")")] n_{0}$ . It states an asymptotic lower bound.
$f (n) = Θ (g (n))$ means that both $f (n) = O (g (n))$ and $f (n) = Ω (g (n))$ hold. It states equality of asymptotic growth rates up to constant factors.

Thus, $O$ denotes an upper bound and does not necessarily assert a tight growth rate. For example, $3 n + 5 = O (n^{2})$ is true, but $3 n + 5 = Θ (n)$ is more precise.

5Examples

Let $T (n) = 3 n + 5$ . For $n [PARSE ERROR: Undefined("Command(\"ge\")")] 1$ ,

3 n [PARSE ERROR: Undefined("Command(\"le\")")] T (n) [PARSE ERROR: Undefined("Command(\"le\")")] 8 n,

so $T (n) = Θ (n)$ . Constant terms and constant factors do not alter the asymptotic growth rate.

For linear search on an array of length $n$ , a match at the first element gives a best-case running time of $Θ (1)$ , while a match only at the final element or no match gives a worst-case running time of $Θ (n)$ . By contrast, binary search on a sorted array halves the candidate interval at each comparison. After $k$ comparisons, at most $n / 2^{k}$ candidates remain, yielding a worst-case running time of $Θ (\log (n + 1))$ , including the empty-array case.

An algorithm that only reads its input and uses a fixed number of variables has auxiliary-space complexity $Θ (1)$ . Allocating another array of length $n$ requires $Θ (n)$ auxiliary space. Time and space must be analyzed separately.

6Connections to Subsequent Lectures

The next lecture derives the time and auxiliary-space complexity of recursion from the number of recursive calls and the maximum call depth. The subsequent sorting and search lectures compare applicability conditions, correctness, and complexity together.

data/lecture/information/algorithm/foundation/recursion-basics.lecture.n.md

7Summary

Input size must be defined by a measure appropriate to the problem.
Time and space complexity measure different computational resources.
Best, average, and worst cases classify inputs; $O$ , $Θ$ , and $Ω$ describe asymptotic relations between functions.
$O$ gives an upper bound, $Ω$ gives a lower bound, and $Θ$ gives a matching upper and lower bound.