データ構造-漸近解析

アルゴリズムの漸近解析とは、実行時のパフォーマンスの数学的境界/フレーミングを定義することです。漸近解析を使用して、アルゴリズムのベストケース、平均ケース、最悪ケースのシナリオを非常によく結論付けることができます。

漸近解析は入力境界です。つまり、アルゴリズムへの入力がない場合、一定時間で機能すると結論付けられます。「入力」以外のすべての要因は一定と見なされます。

漸近解析とは、計算の数学的単位で任意の操作の実行時間を計算することです。たとえば、ある操作の実行時間は_f_（n）として計算され、別の操作の実行時間は_g_（n ^ 2 ^）として計算される場合があります。これは、 n の増加に伴い最初の操作の実行時間が線形に増加し、 n が増加すると2番目の操作の実行時間が指数関数的に増加することを意味します。同様に、 n が非常に小さい場合、両方の操作の実行時間はほぼ同じになります。

通常、アルゴリズムに必要な時間は3種類に分類されます-

ベストケース-プログラムの実行に必要な最小時間。
平均ケース-プログラムの実行に必要な平均時間。
最悪のケース-プログラムの実行に必要な最大時間。

漸近記法

以下は、アルゴリズムの実行時間の複雑さを計算するために一般的に使用される漸近表記法です。

Ο表記
Ω表記
θ表記

Big Oh Notation、Ο

表記Ο（n）は、アルゴリズムの実行時間の上限を表す正式な方法です。最悪の場合の時間の複雑さ、またはアルゴリズムが完了するまでにかかる可能性のある最長時間を測定します。

ビッグO表記

たとえば、関数* f（n）*の場合

Ο(f(n)) = { g(n) : there exists c > 0 and n0 such that f(n) ≤ c.g(n) for all n > n0. }

オメガ表記、Ω

表記Ω（n）は、アルゴリズムの実行時間の下限を表す正式な方法です。これは、最適な時間の複雑さ、またはアルゴリズムが完了するまでにかかる可能性のある最適な時間を測定します。

オメガ表記

たとえば、関数* f（n）*の場合

Ω(f(n)) ≥ { g(n) : there exists c > 0 and n0 such that g(n) ≤ c.f(n) for all n > n0. }

シータ表記、θ

表記法θ（n）は、アルゴリズムの実行時間の下限と上限の両方を表す正式な方法です。次のように表されます-

シータ表記法

θ(f(n)) = { g(n) if and only if g(n) =  Ο(f(n)) and g(n) = Ω(f(n)) for all n > n0. }

一般的な漸近記法

以下は、いくつかの一般的な漸近表記法のリストです-

constant	−	Ο(1)
logarithmic	−	Ο(log n)
linear	−	Ο(n)
n log n	−	Ο(n log n)
quadratic	−	Ο(n²)
cubic	−	Ο(n³)
polynomial	−	n^Ο(1)
exponential	−	2^Ο(n)

Data-structures-algorithms-asymptotic-analysis

目次