1. 序章

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

2. 正式な定義

定義： f（x）= O（g（x））は、x1とcの2つの正の定数が存在することを意味します。すべてのx≥x1に対して0≤f（x）≤cg（x）となるようにします。

3. 最初の正の定数： x1

f（x）= O（g（x））と言うとき、「xのfは大きい-xのOg」と言います。

等号に惑わされないでください。f（x）は関数であり、 O（g（x））はセットです。 セットに等しい関数を持つことはできません。 それは、地球が太陽系に等しいと言っているようなものです。 それは、地球が太陽系（を構成する惑星のセット）に属しているようなものです。 同様に、 f（x）は、 x のO（g（x））（ big-O gと呼ばれる関数のセットに属します。 ]）。

現在、 f（x）と g（x）の2つの関数があります。 関数はさまざまな速度で成長します。たとえば、2次関数は1次関数よりも速く成長します。 しかし二次方程式が追いつくまでに時間がかかる場合があります。

たとえば、 a（x）= 2×2 + 2x + 1およびb（x）= 10x の場合、 a（1）=5[になります。 X101X]およびb（1）=10。 しかし、今、 x =15を選択するとします。 これで、 a（15）= 450 + 30 + 1 = 481およびb（x）=150になります。 さらに、 x = 15より大きい値、たとえばx = 20の場合、a（x）はb（x）よりも大きくなります。（ここで、正式な定義を参照する良い機会です。 ;これはx≥x1の部分です）。

big-Oを正式に理解する場合に重要なのは、どの時点でa（x）がb（x）よりも大きくなり始めたかは特に気にしないことです。 b（x）よりも大きくなり続けます。

4. 2番目の正の定数： c   

上で見たのは、 斧） 追いつくために b（x）。 最終的にはそうなりましたが、しばらく時間がかかりました。

それが最終的に速く成長する理由は、2×2用語のためです。 または、より正確には、そのx2部分です。 これは、a（x）= O（x2）。元の定義の記号を使用することを示しています： f（x）= a（x）および g（x ）=x2。

big-Oの場合、 a（x）の他の項、または2×2項の定数2は関係ありません。

セクション2の定義をもう一度見てみると、ここで定数cが出てきます。 任意の正の定数でg（x）をスケーリングできます– f（x）がスケーリングされたバージョンよりも小さいままである限り（特定のポイントを過ぎて、x≥x1[ X150X]）。

d（x）= 3×3 + 2x + 10、とすると、[X101X]cとx1の値をdとなるように見つける必要があります。 （x）≤cx3 x1より大きいすべての値。これは、セクション4で行っていることとまったく同じです。

5. ピースをまとめる

f（x）= O（g（x））を証明するには、cとx1の2つの正の定数を見つける必要があります。 X121X]0≤f（x）≤cg（x）すべてのx≥x1。不等式が成り立つようにcとx1の値を見つける必要があります。

つまり、特定のポイントを過ぎると、 g（x）のスケーリングされたバージョンは常に f（x）よりも大きくなります。

6. 例

d （x）= 3×3 + 2x +10とします。

d （x）= O（x3）であることを証明したいとします。 これは、すべてのx≥x1[に対して0≤d（x）≤cx3となる2つの正の整数cとx1を見つける必要があることを意味します。 X130X]。

さて、d （x）= 3×3 +2x+10≤3×3+2×3+ 10×3 =15×3であることがわかります。

それで、

d（x）≤15×3。

したがって、 x1 =1およびc= 15、を設定すると、x≥x1 、0≤d（x）≤ cx3。 したがって、 d（x）= O（x3）。

上記の条件を満たすx1とcの他の値を見つけることができました。 重要なのは、条件を満たすx1とcの値が存在することです。

7. 結論

この記事では、ビッグO表記法の理論の紹介に焦点を当てました。

このトピックのより実用的な見方は、ここにあります。