Python-アルゴリズムタイプ

アルゴリズムの効率と精度を分析して、それらを比較し、特定のシナリオに対して特定のアルゴリズムを選択する必要があります。この分析を行うプロセスは、漸近分析と呼ばれます。これは、計算の数学的単位で任意の操作の実行時間を計算することを指します。たとえば、ある操作の実行時間はf（n）として計算され、別の操作の実行時間はg（n2）として計算される場合があります。これは、最初の操作の実行時間がnの増加とともに線形に増加し、2番目の操作の実行時間がnが増加すると指数関数的に増加することを意味します。同様に、nが非常に小さい場合、両方の操作の実行時間はほぼ同じになります。

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

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

漸近記法

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

Ο表記
Ω表記
θ表記

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)

Python-data-structure-python-big-o-notation

目次