計算複雑性理論
計算複雑性理論（けいさんふくざつせいりろん、computational complexity theory）とは、計算機科学における計算理論の一分野であり、アルゴリズムのスケーラビリティや、特定の計算問題の解法の複雑性（計算問題の困難さ）などを数学的に扱う。計算量理論、計算の複雑さの理論、計算複雑度の理論ともいう。
出典: フリー百科事典『ウィキペディア（Wikipedia）』
計算量 complexity
「複雑性」とは、あるアルゴリズムがどれくらい速いかをざっくりと表す指標のことです。
ここでは、複雑性 complexity を、wikipedia での表現に倣い「計算量」と書くことにします。計算量は、空間計算量と時間計算量に分かれます。
空間計算量 space complexity
あるアルゴリズムが「どれぐらいメモリを使うか」が空間計算量です。
時間計算量 time complexity
あるアルゴリズムが「どれぐらい時間を使うか」が時間計算量です。
時間計算量の重要性
「メモリの価格」と「時間の価格」を比較した場合、現在は「メモリの価格」はかなり安くなったため、問題を解く場合は、「時間計算量」が問題になることが多いです。
時間計算量の比較
コンピュータの性能により同じ問題でも処理時間は異なるので、「問題を解くために必要なステップ数」を時間計算量として考えます。
入力サイズ
時間計算量は、入力データ量に対する関数として表されます。つまり、「入力サイズの増加に従って、実行時間がどれぐらい増えるか 」を考えます。
例えば、「入力サイズ 10 で、実行時間 10ms」のアルゴリズムを考えます。このアルゴリズムで、入力サイズが 100 にした場合、実行時間が 100ms であれば線形、実行時間が 1000ms であれば 2乗、 実行時間が10000ms であれば 3乗 の時間計算量となり、それぞれ\(O(n)\)、\(O(n^2)\)、 \(O(n^3)\)、と表現されます。
入力サイズが増加しても実行時間の増加が少ない方が良いアルゴリズムとなります。
