前提条件 – 漸近表記 、 漸近表記の性質 、 アルゴリズムの分析
1. ビッグオー表記 (O):

これは上限として定義され、アルゴリズムの上限は必要な最大時間 (最悪の場合のパフォーマンス) です。
ビッグオー表記 を説明するために使用されます 漸近的な上限 。

数学的に言うと、 f(n) アルゴリズムの実行時間を説明します。 f(n) は O(g(n)) 正の定数が存在する場合 C そして n0 そのような、

0 <= f(n) = n0

n = 関数の上限を与えるために使用されます。
関数が の上） 、自動的に O(n-2乗) 同じように。

グラフィックの例 ビッグオー：

Javaでのオブジェクトの等価性

2. ビッグオメガ表記 (Ω) :

これは下限として定義され、アルゴリズムの下限は必要な時間の最小値です (可能な限り最も効率的な方法、言い換えれば最良の場合)。
と同じように ○ 表記法 提供する 漸近的な上限 、 おお 表記法 提供します 漸近下限 。

させて f(n) アルゴリズムの実行時間を定義します。
f(n) であると言われています Ω(g(n)) 正の定数が存在する場合 C そして (n0) そのような

0 <= Cg(n) = n0

Javaの型キャストと型変換

n = 関数の指定された下限に使用されます
関数が Ω(n二乗) それは自動的に ああ（ん） 同じように。

グラフィカルな例 ビッグオメガ (Ω):

3. ビッグシータ表記 (Θ) :

これは最も厳しい限界として定義され、最も厳しい限界は、アルゴリズムがかかる可能性のあるすべての最悪の場合の時間のうちの最良の時間です。

させて f(n) アルゴリズムの実行時間を定義します。
f(n) であると言われています Θ(g(n)) もし f(n) は O(g(n)) そして f(n) は Ω(g(n))。

数学的には、

0 <= f(n) = n0
0 <= C2g(n) = n0

両方の方程式を結合すると、次のようになります。

0 <= C2g(n) <= f(n) = n0

この方程式は、f(n) が C2 g(n) と C1g(n) の間に挟まれるような正の定数 C1 と C2 が存在することを単に意味します。

の図例 ビッグシータ (Θ) :

Pythonコンストラクター

ビッグオー、ビッグオメガ、ビッグシータの違い:

詳細については、以下を参照してください。 アルゴリズムの設計と解析 。