Looking for algorithm Answers? Try Ask4KnowledgeBase
Looking for algorithm Keywords? Try Ask4Keywords

algorithmBig-O表記法


備考

定義

Big-O表記は、関数の収束率を比較するために使用される数学的表記法を中心としています。 n -> f(n)n -> g(n)自然数に対して定義された関数とする。次に、nが無限に近づいたときにf(n)/g(n)が有界である場合に限り、 f = O(g)と言います。言い換えれば、すべてのnに対してf(n)/g(n) <= Aとなるような定数Aが存在する場合に限り、 f = O(g)となる。

実際にBig-O表記の範囲は数学では多少幅がありますが、簡単にするために、アルゴリズムの複雑さの分析に使用されているものに絞っています。すなわち、自然に定義された関数、非ゼロの値を持つ関数、無限に。

どういう意味ですか ?

f(n) = 100n^2 + 10n + 1g(n) = n^2の場合を考えてみましょう。 nが無限になるにつれて、これらの関数の両方が無限になる傾向があることは明らかです。しかし時には限界を知るだけでは不十分であり、関数が限界に近づく速度も知りたい。 Big-Oのような概念は、収束のスピードによって関数を比較し、分類するのに役立ちます。

この定義を適用してf = O(g)かどうか調べてみましょう。 f(n)/g(n) = 100 + 10/n + 1/n^2 。以来、 10/n 、nが1であり、減少され、そしてためとき10で1/n^2 、nが1であり、また、減少しているとき1であり、我々はf(n)/g(n) <= 100 + 10 + 1 = 111f(n)/g(n) (111)とf = O(g)境界が見つかったため、定義は満たされます(fはn^2 Big-Oです)。

これは、fがgとほぼ同じ速度で無限大になることを意味する。今、これは奇妙なことに思えるかもしれません。私たちが見つけたのは、fはgよりも111倍大きく、言い換えればgが1だけ大きくなると、fは大きくても111倍になるからです。 111倍速くても「ほぼ同じ速度」ではありません。 Big-O表記法は関数収束速度を非常に正確に分類する方法ではありません。そのため、正確な速度推定が必要な場合には数学で等価関係を使用します。しかし、高速クラスでアルゴリズムを分離する目的で、Big-Oで十分です。私たちは、相互に固定された回数だけ成長する関数を分離する必要はなく、互いに無限に速く成長する関数だけを分離する必要があります。我々が取る場合、例えばh(n) = n^2*log(n) 、我々はそれを参照してh(n)/g(n) = log(n) hがOではないので、nは無限大になる傾向がある(N ^を2)は、hがn ^ 2よりも無限に速く成長するためです。

ここで、 f = O(g)g = O(h)場合、 f = O(h)ことに気づいたかもしれません。私たちの場合たとえば、私たちがしているf = O(n^3)およびf = O(n^4) ...アルゴリズムの複雑性分析では、我々は頻繁に言うf = O(g)ことを意味するとf = O(g) g = O(f)であり、これは「gはfの最小のBig-O」と理解できる。数学では、そのような関数はお互いのビッグ・テータであると言います。

どのように使用されていますか?

アルゴリズムの性能を比較する場合、アルゴリズムが実行する操作の数に関心があります。これは時間の複雑さと呼ばれています 。このモデルでは、基本的な演算(加算、乗算、比較、代入など)に一定の時間がかかることを考慮し、その数を数えます。通常、この数値は入力のサイズの関数として表現できます。これはnと呼ばれます。そして、悲しいことに、この数は通常nで無限になります(アルゴリズムがO(1)であるとは言えません)。 Big-Oで定義されたビッグスピードクラスでアルゴリズムを分離します。「O(n ^ 2)アルゴリズム」について言及するとき、それが実行する操作の数はnの関数として表され、O( n ^ 2)。これは、我々のアルゴリズムが、入力の大きさの2乗に等しい数の演算を行うアルゴリズムとほぼ同じくらい高速であることを示しています 。私がBig-Thetaの代わりにBig-Oを使用したので、「より速い」部分がありますが、通常、Big-OはBig-Thetaを意味します。

演算をカウントするときには、通常、最悪の場合を考慮します。たとえば、最大n回実行できるループがあり、5回の演算を含むループがある場合、カウントする演算の数は5nです。また、平均的なケースの複雑さを考慮することも可能です。

クイック注:高速アルゴリズムは、いくつかの動作を行うものであるので、操作の数が速く無限に成長する場合、アルゴリズムは遅い :O(n)がOよりも良好である(N ^ 2)。

私たちは時にはアルゴリズムの空間複雑さにも興味があります。このために、アルゴリズムの占有するメモリ内のバイト数を入力のサイズの関数として考慮し、同様にBig-Oを使用します。

Big-O表記法 関連する例