Big-O表記とLittle-o表記の違い

1. 概要

この簡単なチュートリアルでは、big-O表記とlittle-o表記の違いについて学習します。つまり、これらは両方とも、関数の上限とアルゴリズムの実行時間を指定する漸近表記です。

ただし、違いは、 big-Oが漸近的にタイトであるのに対し、little-oは上限が漸近的にタイトでないことを確認することです。

漸近的にタイトであることが正確に何を意味するのかを理解するために読み進めましょう。

Big-O表記とlittle-o表記の定義は非常に似ており、それらの違いは、それらが表す上限に関してどれほど厳密であるかにあります。

特定の関数について、は次のように定義されます。

すべてのに対して正の定数などが存在します。

So は関数のセット、つまりの後、は以下です。 big-O表記（またlittle-o表記）は関数の膨大な数を分析するため、以前の関数の動作は重要ではありません。例として、次の図を見てみましょう。

ここでは、に属する可能な関数の1つにすぎません。の前は、常に。以下であるとは限りませんが、後は、を超えることはありません。

定義の等号は、 無症候性の気密性の概念を表します。は、 が非常に大きくなると、およびを意味します。 ]同じ速度で成長します。たとえば、は等号を満たしているため、漸近的にタイトですが、そうではありません。

この表記法の詳細については、ビッグO表記法の理論の概要を参照してください。

Little-o表記は、漸近的にタイトではない上限を示すために使用されます。正式には次のように定義されています。

任意の正の定数に対して、すべてのに対して次のような正の定数が存在します。

この定義では、関数のセット はよりも厳密に小さいことに注意してください。は、little-o表記がbig-O表記よりも強い上限。つまり、little-o表記では、関数がと同じ成長率を持つことはできません。

直感的には、これは、無限大に近づくにつれて、に比べて重要ではなくなることを意味します。数学的に：

さらに、little-oの定義の不等式は、任意の定数に当てはまるはずですが、big-Oの場合は、不等式を満たすものを見つけるだけで十分です。

との漸近比較と実数との比較の間にアナロジーを描くと、。

物事をより明確にするためにいくつかの例を見てみましょう。

については、次のようになります。

一般に、の場合、次のようになります。

big-O表記のその他の例については、big-O表記の実用的なJavaの例を参照してください。

この記事では、big-O表記とlittle-o表記の違いを学び、little-o表記がbig-O関数のセットから漸近的にタイトな関数を除外していることに注目しました。