algorithm
Big-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 + 1
とg(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 = 111
。 f(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を使用します。
シンプルなループ
次の関数は、配列内の最大要素を見つけます。
int find_max(const int *array, size_t len) {
int max = INT_MIN;
for (size_t i = 0; i < len; i++) {
if (max < array[i]) {
max = array[i];
}
}
return max;
}
入力サイズは配列のサイズです。これをコードでlen
と呼びます。
操作を数えましょう。
int max = INT_MIN;
size_t i = 0;
これらの2つの割り当ては1回だけ実行されるため、2つの操作です。ループされる操作は次のとおりです。
if (max < array[i])
i++;
max = array[i]
ループには3つの演算があり、ループはn回実行されるので、既存の2つの演算に3n
を足して3n + 2
を得る。したがって、私たちの関数は3n + 2
演算を行い、最大値(複雑さは3n + 2
)を求めます。これは、最も急成長する項がnの因数である多項式なので、O(n)です。
あなたはおそらく、「操作」があまりよく定義されていないことに気づいたでしょう。例えば、私は、 if (max < array[i])
が1つの演算であったが、アーキテクチャに応じて、このステートメントを例えば3つの命令、すなわち1つのメモリ読取り、1つの比較および1つの分岐でコンパイルすることができると述べた。私はまた、たとえメモリ操作が他のものより遅くても、すべての操作を同じと見なしました。そのパフォーマンスは、キャッシュ効果などによって大きく変わります。私はまた、リターンステートメント、フレームが関数などのために作成されるという事実を完全に無視しました。結局のところ、計算をどのように選択するかによって、 n因子と定数の結果はO(n)になります。複雑さは、アルゴリズムが入力のサイズにどのように比例するかを示しますが、パフォーマンスの唯一の側面ではありません。
ネストループ
次の関数は、各要素を取得して配列に重複があるかどうかをチェックし、配列全体を繰り返してその要素がそこにあるかどうかを調べます
_Bool contains_duplicates(const int *array, size_t len) {
for (int i = 0; i < len - 1; i++) {
for (int j = 0; j < len; j++) {
if (i != j && array[i] == array[j]) {
return 1;
}
}
}
return 0;
}
内部ループは、各繰り返しにおいて、 n
で一定である多数の演算を実行する。外側のループもいくつかの一定の操作を行い、内側のループをn
回実行します。外部ループ自体はn
回実行されます。したがって、内側ループ内の演算はn^2
回実行され、外側ループの演算はn
回実行され、 i
への代入は1回実行されます。したがって、複雑さはan^2 + bn + c
ようなものになり、最も高い項はn^2
、O表記はO(n^2)
です。
気づいたことがあるかもしれませんが、同じ比較を何回も繰り返さないようにすることでアルゴリズムを改善することができます。前のすべての要素は、すでにインデックスi + 1
配列要素を含むすべての配列要素に対してチェックされているため、内部ループのi + 1
から開始できます。これにより、 i == j
チェックを削除することができます。
_Bool faster_contains_duplicates(const int *array, size_t len) {
for (int i = 0; i < len - 1; i++) {
for (int j = i + 1; j < len; j++) {
if (array[i] == array[j]) {
return 1;
}
}
}
return 0;
}
明らかに、この2番目のバージョンは操作が少なく、効率的です。それはBig-O記法にどのように変換されますか?さて、内側ループ本体は、 1 + 2 + ... + n - 1 = n(n-1)/2
回実行されます。これはまだ 2次の多項式なので、依然としてO(n^2)
です。私たちが行っている操作の数を2で割ったので、複雑さをはっきりと下げましたが、Big-Oで定義されているのと同じ複雑さのクラスです。複雑さをより低いクラスに下げるためには、操作の数をn
無限になるようなものに分割する必要があります。
O(log n)の例
前書き
次の問題を考えてみましょう。
L
は、 [-5, -2, -1, 0, 1, 2, 4]
(ここではn
は7の値)など、 n
n
符号付き整数( n
は十分に大きい)を含むソートされたリストです。 L
が整数0を含むことがわかっている場合、どのようにしてインデックス0を見つけることができますか?
ナイーブアプローチ
最初に気になるのは、0が見つかるまですべてのインデックスを読み取ることです。最悪の場合、操作の数はn
なので、複雑さはO(n)です。
これはn
小さな値に対してうまく動作しますが、より効率的な方法がありますか?
二分法
以下のアルゴリズム(Python3)を考えてみましょう:
a = 0
b = n-1
while True:
h = (a+b)//2 ## // is the integer division, so h is an integer
if L[h] == 0:
return h
elif L[h] > 0:
b = h
elif L[h] < 0:
a = h
a
とb
は、その間に0が見つかるインデックスです。私たちはループに入るたびに、我々は間のインデックスを使用し、 a
b
と検索するエリアを絞り込むためにそれを使用します。
最悪の場合、 a
とb
が等しくなるまで待たなければなりません。しかし、どれくらいの操作がかかるのでしょうか? N、我々はループに入るたびにので、我々は、距離分裂しないとa
b
約2で。むしろ、複雑さはO(log n)である。
説明
注: "log"と書くと、バイナリ対数、つまりlog base 2( "log_2"と書かれます)を意味します。 O(log_2 n)= O(log n)(あなたが計算することができる)として、 "log_2"の代わりに "log"を使用します。
xを操作の数としましょう:1 = n /(2 ^ x)を知っています。
したがって、2 ^ x = n、x = log n
結論
連続的な分割(2つまたは任意の数で)に直面するとき、複雑さは対数であることを忘れないでください。
O(log n)型のアルゴリズム
サイズnの問題があるとしましょう。現在、アルゴリズムの各ステップ(書き込みが必要)では、元の問題は以前のサイズの半分(n / 2)になります。
だから、それぞれのステップで、私たちの問題は半分になります。
ステップ | 問題 |
---|---|
1 | n / 2 |
2 | n / 4 |
3 | n / 8 |
4 | n / 16 |
問題空間が縮小された(すなわち完全に解かれた)場合、チェック条件を終了しても、それ以上縮小することはできません(nは1に等しくなります)。
k番目のステップまたは操作の数で言えましょう:
問題サイズ = 1
しかし、私たちはk番目のステップで、私たちの問題の大きさは、
問題サイズ = n / 2k
1と2から:
n / 2 k = 1または
n = 2k
両側にログを取る
log e n = k log e 2
または
k = log e n / log e 2
数式ログを使用するx m / log x n = log n m
k = log 2 n
または単にk = log n
今、私たちのアルゴリズムはlog nまで最大で実行できることを知っています。したがって、時間の複雑さは次のようになります。
O(log n)
上記のテキストをサポートするためのコードの簡単な例は次のとおりです。
for(int i=1; i<=n; i=i*2)
{
// perform some operation
}
だから、もしnが256であれば、もしあなたがループしている(または問題の大きさを半分に減らす他のアルゴリズム)ステップ数が非常に簡単に計算できるかどうかを尋ねるなら、
k = log 2 256
k = log 2 2 8 (=> log a a = 1)
k = 8
同様の場合の別の非常に良い例は、 バイナリサーチアルゴリズムです。
int bSearch(int arr[],int size,int item){
int low=0;
int high=size-1;
while(low<=high){
mid=low+(high-low)/2;
if(arr[mid]==item)
return mid;
else if(arr[mid]<item)
low=mid+1;
else high=mid-1;
}
return –1;// Unsuccessful result
}