Big-O記法の理論の紹介

この記事では、big-O表記の数学の紹介とbig-O証明の例を示します。

f（x）= O（g（x））

と言うと、

x

の

f

はbig-O

g

of

x

となります。

等号を惑わさないでください。

f（x）

は関数で、

O（g（x））

は集合です。あなたはセットに匹敵する機能を持つことはできません。地球は太陽系と等しいと言っているのと同じです。それは、地球が太陽系を構成する惑星の集合であることにもっと似ています。

同様に、


f（x）

は

O（g（x））


（

big-O


g

of

x

）と呼ばれる一連の関数に属します。

f（x）

と

g（x）

の2つの関数があります。関数http://bigocheatsheet.com/[さまざまな速度で成長する]。たとえば、2次関数は線形関数よりも速く成長します。しかし、場合によっては、2次方程式が追いつくまでに時間がかかることがあります。

たとえば、

a（x）= 2x ^ 2 ^ 2x 1と

b（x）= 10x

の場合、

a（1）= 5と

b（1）= 10

になります。しかし、今言うと

x = 15

を選択します。これで、

a（15）= 450 30 1 = 481

と

b（x）= 150

になります。さらに、**

x = 15

よりも大きい値の場合、

x = 20

の場合、

a（x）

は

b（x）.

よりも大きくなります。は

x≥x〜1〜

の部分です。

big-Oを形式的に理解する場合、重要なのは、**

a（x）

が

b（x）

を超えて成長し始めた時点では、特に気にしないことです。

b（x）

より大きくなければなりません。

a（x）

が

__b（x）に追いつくのに時間がかかることを上で見ました。

__最終的にはできましたが、しばらく時間がかかりました。

それが結局速く成長する理由は

__2x ^ 2 ^

__termのためです。

あるいは、より正確には、その

x ^ 2 ^

部分です。 ** これは

a（x）= O（x ^ 2 ^）

であることを示しています。

big-Oの場合、

a（x）

の他の項や、

2x ^ 2 ^

項の定数

2

については気にしません。

セクション2からの定義をもう一度見てみると、ここに定数

c

が入っています。ある点、

x≥x〜1〜

）。

d（x）= 3x ^ 3 ^ 2x 10とすると、

xよりも大きいすべての値に対して

d（x）≦cx ^ 3 ^

となるように

c

と

x〜1〜

の値を見つける必要があります。 〜1.〜__これはまさにセクション4で行うことです。

f（x）= O（g（x））

を証明するために、2つの正の定数

c

と

x〜1〜

を見つける必要があります。

x≥x〜1〜

。 ** 不等式が成り立つように

c

と

x〜1〜

の値を見つける必要があります。

それが意味することは、ある点を過ぎると、スケールされたバージョンの

g（x）

は常に

f（x）

より大きくなるということです。

d

__（x）= 3x ^ 3 ^ 2x 10

__とします。

d

__（x）= O（x ^ 3 ^）


であることを証明したいとします。これは、すべての

x≥x〜1〜

に対して

0≤d（x）≤cx ^ 3 ^

となるように、2つの正の整数

c

と

x〜1〜__を見つける必要があることを意味します。

ええと、d


_（x）= 3x ^ 3 ^ 2x 10≤3x ^ 3 ^ 2x ^ 3 ^ 10x ^ 3 ^ = 15x ^ 3 ^

_

そう、

d（x）≦15x ^ 3 ^

。

したがって、


_x〜1〜= 1


と


c = 15を設定すると、

x≥x〜1〜、0≤d（x）≤cx ^ 3 ^

のいずれかになります。だから

d（x）= O（x ^ 3 ^）_

。

上記の条件を満たす

x〜1〜

と

c

の他の値が見つかりました。重要なことは、条件を満たす

x〜1〜

と

c

の値が存在することです。

この記事では、big-O記法の理論の紹介に焦点を当てました。

このトピックのより実用的な外観はhttps://github.com/eugenp/tutorials/tree/master/algorithms-miscellaneous-2[こちらを参照]です。