時間計算量解析のどの表記法を使用すればよいかをどのようにして知ることができるでしょうか?

https://cs.stackexchange.com/questions/57

16-10-2019
|

質問

アルゴリズムの入門クラスのほとんどでは、$O$ (Big O) や $ heta$ などの表記法が導入されており、学生は通常、これらのいずれかを使用して時間計算量を求めることを学びます。

ただし、$o$、$\Omega$、$\omega$ などの他の表記法もあります。ある表記法が別の表記法よりも好ましい特定のシナリオはありますか?

解決

あなたはに言及していますランダウ表記. 。それらは同じことの違いはありませんが、まったく異なる意味を持っています。どれが「好ましい」というのは、望ましいステートメントに完全に依存します。

$ f in cal {o}（g）$は、$ f $が$ g $と同じくらい速く、漸近的で一定の因子まで成長することを意味します。それを$ leq $と考えてください。 $ f in o（g）$はより厳格なフォーム、すなわち$ <$です。

$ f in omega（g）$には対称的な意味があります。$ f $は少なくとも$ g $と同じくらい速く成長します。 $ omega $はより厳しいいとこです。 $ f in omega（g）$が$ g in cal {o}（f）$に相当することがわかります。

$ f in theta（g）$は、$ f $が$ g $ほど速く成長することを意味します。正式に$ f in cal {o}（g） cap omega（g）$。 $ f sim g $（漸近平等）はその強い形です。多くの場合、$ cal {o} $を使用する場合、$ theta $を意味します。

$ cal {o}（g）$とその兄弟がどのようにあるかに注意してください 関数クラス. 。これとそれらの正確な定義を非常に認識することが重要です。これは、誰が話しているかによって異なる場合があります - 彼らと「算術」を行うときです。

物事を証明するときは、正確な定義で作業するように注意してください。ランダウのシンボルには多くの定義があります（すべて同じ基本的な直観を持つ）。その一部は、関数の一部のセットでは同等ですが、他のセットでは同等です。

提案された読書：

Landauの表記法を厳密で健全な方法で使用することに興味がある場合は、Rutanen et al。の最近の研究に興味があるかもしれません。 [1]。それらは、アルゴリズムでそれらを使用するため、漸近表記に必要かつ十分な基準を定式化し、共通の定義がそれらを満たしていないことを示し、（実際に）実行可能な定義を提供します。

アルゴリズム分析のためのOノートの一般的な定義 K.ルタネンら（2015）

他のヒント

ビッグオー:上界

「Big O」（$O$）が最も一般的なものです。アルゴリズムの複雑さを分析する場合、ほとんどの場合、重要なのは上限を設定することです入力のサイズが大きくなると実行時間が長くなる速さ¹。基本的に、アルゴリズムの実行に「時間がかかりすぎる」ことがないことを知りたいのです。これを実際の時間単位 (秒) で表すことはできません。それは、正確な実装 (プログラムの書き方、コンパイラーの性能、マシンのプロセッサーの速さなど) に依存するためです。したがって、そのような詳細に依存しないもの、つまり、より大きな入力をアルゴリズムに入力したときにアルゴリズムの実行にどれだけ時間がかかるかを評価します。そして、私たちが主に気にするのは、プログラムがいつ完了したかを確信できるかどうかです。そのため、通常は、これこれの時間がかかるか、それ以下であるかを知りたいと考えます。

入力サイズ $n$ に対してアルゴリズムの実行時間が $O(f(n))$ であるということは、アルゴリズムが最大 $K \, f(n で完了するような定数 $K$ が存在することを意味します)$ ステップ、つまりアルゴリズムの実行時間は、最大で $f$ の速度で増加します (スケーリング係数まで)。入力サイズ $n$ に対するアルゴリズムの実行時間 $T(n)$ に注目すると、$O(n)$ は、非公式には、あるスケーリング係数までの $T(n) \le f(n)$ を意味します。

下限

場合によっては、上限よりも多くの情報があると便利です。$\Omega$ は $O$ の逆です。これは、ある関数が少なくとも別の関数と同じ速度で成長することを表します。$T(n) = \Omega(g(n))$ は、ある定数 $K'$ に対して $T(N) \ge K' g(n)$ を意味します。非公式に言うと、$T(n) \ge g(n)$ はある倍率までです。

アルゴリズムの実行時間を正確に決定できる場合、$ heta$ は $O$ と $\Omega$ を組み合わせます。これは、関数の成長速度が既知で、スケール係数まで。$T(n) = heta(h(n))$ は、一部の定数 $K$ と $K'$ に対して $K h(n) \ge T(n) \ge K' h(n)$ を意味します。非公式に言えば、ある倍率までは $T(n) \ほぼ h(n)$ です。

さらなる考慮事項

「小さな」$o$ と $\omega$ は、複雑さの分析ではあまり使用されません。小さな $o$ は大きな $O$ よりも強いです。ここで、$O$ は成長がそれほど速くないことを示し、$o$ は成長が厳密に遅いことを示します。逆に、$\omega$ は厳密により速い成長を示します。

上記の議論では少し非公式になってしまいました。ウィキペディアには正式な定義とより数学的なアプローチがあります。

$T(n) = O(f(n))$ などで等号を使用するのは誤りであることに注意してください。厳密に言えば、$O(f(n))$ は変数 $n$ の関数の集合であり、$T \in O(f)$ と書く必要があります。

例：いくつかの並べ替えアルゴリズム

かなり無味乾燥なので、例を挙げてみましょう。ほとんどの並べ替えアルゴリズムには、二次関数の最悪の場合の実行時間があります。サイズが $n$ の入力の場合、アルゴリズムの実行時間は $O(n^2)$ です。例えば、選択ソート $k$ 番目の要素を選択するには $n-k$ の比較、合計 $n(n-1)/2$ の比較が必要なため、実行時間は $O(n^2)$ となります。実際、比較の回数は常に正確に $n(n-1)/2$ となり、$n^2$ として増加します。したがって、選択ソートの時間計算量をより正確に知ることができます。それは $ heta(n^2)$ です。

さあ、取ってくださいマージソート. 。マージソートも 2 次 ($O(n^2)$) です。これは真実ですが、あまり正確ではありません。実際、マージソートの実行時間は $O(n \:最悪の場合は \mathrm{lg}(n))$ になります。選択ソートと同様、マージソートのワークフローは基本的に入力の形状に依存せず、その実行時間は常に $n \:\mathrm{lg}(n)$ は定数乗算係数まで、つまりそれは $ heta(n \:\mathrm{lg}(n))$。

次に考えてみましょうクイックソート. 。クイックソートはさらに複雑です。確かに $O(n^2)$ です。さらに、クイックソートの最悪のケースは 2 次です。の 最悪の場合 は $\シータ(n^2)$ です。ただし、クイックソートの最良のケース (入力がすでにソートされている場合) は線形です。一般にクイックソートの下限として言えることは $\Omega(n)$ です。ここでは証明を繰り返しませんが、平均複雑クイックソート (入力の可能なすべての順列の平均) は $ heta(n \:\mathrm{lg}(n))$。

一般的な設定における並べ替えアルゴリズムの複雑さに関する一般的な結果があります。並べ替えアルゴリズムは一度に 2 つの要素しか比較できず、結果は Yes または No ($x \le y$ または $x > y$) になると仮定します。この場合、アルゴリズムはどこに適合するかを知るためにすべての要素を少なくとも 1 回比較する必要があるため、ソートアルゴリズムの実行時間は常に $\Omega(n)$ ($n$ はソートする要素の数) であることがわかります。。たとえば、入力がすでに並べ替えられており、アルゴリズムが単に各要素を次の要素と比較して順序を維持する場合 (つまり、$n-1$ 比較)、この下限を満たすことができます。あまり明らかではないのは、最大実行時間は必然的に $\Omega(n \:\mathrm{lg}(n))$。アルゴリズムが行う比較の数が少なくなる可能性もありますが、任意の入力サイズ $n$ に対して、アルゴリズムが $K n \mathrm{ lg}(n)$ の比較。証明の考え方は、アルゴリズムの決定木を構築することです。各比較の結果からアルゴリズムが下した決定に従います。各比較では「はい」または「いいえ」の結果が返されるため、決定木は二分木になります。入力には $n!$ 個の可能な順列があり、アルゴリズムはそれらすべてを区別する必要があるため、決定木のサイズは $n!$ になります。ツリーはバイナリツリーであるため、これらすべてのノードに適合するには $ heta(\mathrm{lg}(n!)) = heta(n\:\mathrm{lg}(n))$ の深さが必要です。深さはアルゴリズムが行う決定の最大数であるため、アルゴリズムの実行には少なくとも次の数の比較が含まれます。最大実行時間は $\Omega(n \:\mathrm{lg}(n))$。

¹ _{またはメモリ空間などのその他のリソースの消費。この回答では、実行時間のみを考慮します。}

通常、$ o $は上限（上からの推定値）を記載するために使用されますが、$ omega $は下限（下からの見積もり）を述べるために使用され、$ theta $は一致するときに使用されます。ケース（通常）の代わりに$ theta $を使用して、結果を述べることができます。

ライセンス： CC-BY-SA と帰属

所属していません cs.stackexchange