アルゴリズム複雑度分析

アルゴリズム複雑度解析(複雑性解析)は、実装を必要とせずにすべての入力を考慮できる方法であり、ハードウェアの実行環境やソフトウェア環境にかかわらず、アルゴリズムの効率を評価することができる.
アルゴリズムの効率は,アルゴリズムが結果に至るまでの実行時間やコンピュータメモリなどのリソースの使用効率である.

1.時間複雑度関数

アルゴリズム解析は,実行時間,必要な記憶空間量,およびこの2つの側面を考慮する.アルゴリズムの実行時間解析を時間複雑度(時間複雑度)と呼び,アルゴリズムが使用する記憶空間解析を空間複雑度(空間複雑度)と呼ぶ.アルゴリズムの複雑さについては、通常、時間の複雑さを指す.
時間の複雑さは,アルゴリズムを構成する演算が何回実行されるかを数値で表す.通常、演算の実行回数は一定の数字(定数)ではありません.𝑛関数になります.入力されたオペランド𝑛表示される関数は時間複雑度関数と呼ばれ、𝑇(𝑛)と表記される.

2.Big-O記号

通常入力数𝑛時間複雑度関数𝑇(𝑛)との関係はかなり複雑である可能性がある.しかし,入力資料の個数が大きいと,差が最も大きい項が全体の値を支配していることがわかる.したがって,一般的には,時間複雑度関数において,車次最大の港湾を考慮すれば十分である.
時間複雑度関数から不要な情報を除去するためにアルゴリズム解析を容易にするために,時間複雑度を表す方法をBig−Oマーキング法と呼ぶ.例えば、アルゴリズム𝑛これに比例した実行時間を持つというよりも,このアルゴリズムの時間複雑度は𝑂(n)である.この表記法.𝑛関数の上限値を表す方法.
Big-O記号の数学的定義は以下の通りである.
2つの関数𝑓(𝑛)および𝑔(𝑛)が与えられると、すべての𝑛 ≥ 𝑛0について、|𝑓(𝑛)| ≤ 𝑐|𝑔(𝑛)|を満たす2つの定数𝑐および𝑛0が存在する場合、𝑓(𝑛) = 𝑂(𝑔(𝑛))となる.
例:

전제 :
|𝑓(𝑛)| ≤ 𝑐|𝑔(𝑛)| 을 증명할 수 있으면 𝑓(𝑛) = 𝑂(𝑔(𝑛)) 은 True

예제 :
𝑓(𝑛) = 2𝑛² + 3, 𝑔(𝑛) = 𝑛² 일 때 𝑓(𝑛) = 𝑂(𝑔(𝑛)) 가 성립하는지 증명해보자.
|𝑓(𝑛)| ≤ 𝑐|𝑔(𝑛)| 을 증명할 수 있으면 True

풀이 :
2𝑛² + 3 ≤ 𝑐 × 𝑛²
𝑐 = 1 이면 𝑛²		(×)
𝑐 = 2 이면 2𝑛²	(×)
𝑐 = 3 이면 3𝑛²	⬇

𝑛		2𝑛² + 3		  3𝑛²
--------------------------
1	   2·1²+3=5		3·1²=3		(×)
2	   2·2²+3=11	3·2²=12		(o)		n ≥ 2
3	   3·3²+3=21	3·3²=27		(o)

∴ 𝑓(𝑛) = 𝑂(𝑔(𝑛)) 은 true when 𝑐 = 3 and n ≥ 2

Big−Oマーキング法を用いると,時間複雑度関数の増大に寄与しない項を省略でき,時間複雑度の表現を簡略化できる.得られた方法は,基本演算の回数を多項式で表すと多項式の高次港湾を残し,他の項と定数項を捨てることである.最上位次項の係数を抜き、最上位次項の次項のみを使用します.でも注意したいのはロゴ𝑛つまり、銀を消すことはできません.log𝑛彼は度数があるからだ.
次に、一般的なBig-Oマーキング法を順番に表示します.

𝑂(1):一定

𝑂(log𝑛) : ログ型

𝑂(𝑛) : 線形

𝑂(𝑛log𝑛) : 線形ログ

𝑂(𝑛²) : 第2世代

𝑂(𝑛³) : 第3世代

𝑂(2^𝑛) : 指数

𝑂(𝑛!) : 工場レベル

次はアルゴリズム実行時間の比較です.

𝑂(1) < 𝑂(log𝑛) < 𝑂(𝑛) < 𝑂(𝑛log𝑛) < 𝑂(𝑛²) < 𝑂(2^𝑛) < 𝑂(𝑛!)

3Ω符号

実際,Big−Oマーキング法はマーキング上限であり,上限は複数存在する可能性がある.しかし,Big−Oマーキング法が最小回数としてマーキングされた場合にのみ意味がある.従って,これらの問題を補うためにはΩ(Big‐Omega)符号を用いる必要がある.Θ大きいサイズがありますBig-Omegaマーキング法は,ある関数の下限を表す方法である.
Big−Oの場合、𝑓(𝑛) = 2𝑛 + 1を𝑓(𝑛) = 𝑂(𝑛)と呼ぶが、実際には𝑓(𝑛) = 𝑂(𝑛²)と呼ぶこともできる.𝑛0 = 1,𝑐 = 2は𝑛 > 1を表すからである.ただし、Big-Omegaについては、2𝑛 + 1 ≤ 2𝑛²が𝑓(𝑛) = 2𝑛 + 1を表し、𝑛 > 1を表す.
Big-Omegaマーキング法の数学的定義は以下の通りである.
2つの関数2𝑛 + 1 ≥ 𝑛および𝑓(𝑛) = Ω(𝑛)が与えられると、すべての𝑓(𝑛)について、𝑔(𝑛)を満たす2つの定数𝑛 ≥ 𝑛0および|𝑓(𝑛)| ≥ 𝑐|𝑔(𝑛)|が存在する場合、𝑐となる.
例:

전제 :
|𝑓(𝑛)| ≥ 𝑐|𝑔(𝑛)| 을 증명할 수 있으면 𝑓(𝑛) = Ω(𝑔(𝑛)) 은 True

예제 :
𝑓(𝑛) = 2𝑛² + 3, 𝑔(𝑛) = 𝑛² 일 때 𝑓(𝑛) = Ω(𝑔(𝑛)) 가 성립하는지 증명해보자.
|𝑓(𝑛)| ≥ 𝑐|𝑔(𝑛)| 을 증명할 수 있으면 True

풀이 :
2𝑛² + 3 ≥ 𝑐 × 𝑛²
𝑐 = 1 이면 𝑛²		(o)

𝑛		2𝑛² + 3		  𝑛²
--------------------------
1	   2·1²+3=5		1²=1		(o)

∴ 𝑓(𝑛) = Ω(𝑔(𝑛)) 은 true

4. Θ大きいサイズ

Θ(Big-Theta)上限と下限、すなわち𝑛0,𝑓(𝑛) = Ω(𝑔(𝑛))を同じ関数で作成できる場合、𝑓(𝑛) = 𝑂(𝑔(𝑛))と呼ぶ.例えば、𝑓(𝑛) = Ω(𝑔(𝑛))であれば、𝑓(𝑛) = Θ(𝑔(𝑛))は𝑓(𝑛) = 2𝑛 + 1に対応するので、𝑛 > 1である.
Big-Thetaマーキング法の数学的定義は以下の通りである.
2つの関数𝑛 ≤ 2𝑛 + 1 ≤ 3𝑛および𝑓(𝑛) = Θ(𝑛)が与えられると、すべての𝑓(𝑛)について、𝑔(𝑛)を満たす3つの定数𝑛 ≥ 𝑛0、𝑐1|𝑔(𝑛)| ≤ |𝑓(𝑛)| ≤ 𝑐2|𝑔(𝑛)|および𝑐1が存在する場合、𝑐2となる.𝑛0𝑓(𝑛) = Θ(𝑔(𝑛))True&𝑓(𝑛) = Θ(𝑔(𝑛))Trueが成立する.
References

『C言語の分かりやすい資料構造』