Big-O に関する私の知識は限られているため、方程式に対数項が現れると、さらに気が遠くなります。
O(log n)誰かがアルゴリズムとは何かを簡単に説明できますか? 対数はどこから来ますか?
これは、この中間の練習問題を解こうとしていたときに具体的に出てきました。
X(1..n) と Y(1..n) に整数の 2 つのリストが含まれ、それぞれが減少しない順序で並べ替えられているとします。O(log n) 時間のアルゴリズムを与えて、結合された 2n 個の要素すべての中央値 (または n 番目に小さい整数) を見つけます。たとえば、X = (4, 5, 7, 8, 9) および Y = (3, 5, 8, 9, 10) の場合、7 は組み合わせたリスト (3, 4, 5, 5, 7) の中央値です。 、8、8、9、9、10)。[ヒント: 二分探索の概念を使用]
O(log n) アルゴリズムを初めて目にするのはかなり奇妙だということに同意しなければなりません...その対数はいったいどこから来たのでしょうか? ただし、対数項を big-O 表記で表示するには、いくつかの方法があることがわかりました。ここにいくつかあります：
任意の数 n を取ります。たとえば、16. n を 2 で割ると、1 以下の数値が得られますか? 16 の場合、
16 / 2 = 8
8 / 2 = 4
4 / 2 = 2
2 / 2 = 1
これを完了するには 4 つの手順が必要になることに注意してください。興味深いことに、log 2 16 = 4もあります。うーん... 128 はどうですか?
128 / 2 = 64
64 / 2 = 32
32 / 2 = 16
16 / 2 = 8
8 / 2 = 4
4 / 2 = 2
2 / 2 = 1
これには 7 つのステップが必要で、log 2 128 = 7 でした。これは偶然ですか? いいえ！これには正当な理由があります。数 n を 2 で i 回割るとします。次に、数 n / 2 iを取得します。この値が最大で 1 である i の値を解きたい場合、次のようになります。
n / 2 i ≤ 1
n ≤ 2 i
log 2 n ≤ i
つまり、i ≥ log 2 n となる整数 i を選択すると、n を i 回半分に分割した後、最大で 1 の値が得られます。これが保証される最小の i は、おおよそ log 2です。 n であるため、数が十分に小さくなるまで 2 で割るアルゴリズムがある場合、O(log n) ステップで終了すると言えます。
重要な点は、n をどの定数で割るか (1 より大きい限り) は問題ではないということです。定数 k で除算すると、1 に到達するまでに log k n ステップかかります。したがって、入力サイズを分数で繰り返し除算するアルゴリズムは、O(log n) 回の反復を終了する必要があります。これらの反復には多くの時間がかかる可能性があるため、正味実行時間は O(log n) である必要はありませんが、ステップ数は対数になります。
では、これはどこで発生しますか？古典的な例の 1 つは、二分探索です。これは、並べ替えられた配列から値を検索するための高速アルゴリズムです。アルゴリズムは次のように機能します。
たとえば、配列で 5 を検索するには
1 3 5 7 9 11 13
最初に中間要素を見てみましょう。
1 3 5 7 9 11 13
^
7 > 5 であり、配列が並べ替えられているため、5 という数値が配列の後半にあることはあり得ないことがわかっているので、それを破棄することができます。この葉
1 3 5
それでは、ここで中央の要素を見てみましょう。
1 3 5
^
3 < 5 であるため、配列の前半に 5 が表示されないことがわかっているため、前半の配列をスローして終了できます。
5
再び、この配列の中央を見てみましょう。
5
^
これはまさに私たちが探している数であるため、5 が実際に配列にあると報告できます。
では、これはどのくらい効率的ですか？各反復で、残りの配列要素の少なくとも半分を破棄しています。アルゴリズムは、配列が空になるか、必要な値が見つかるとすぐに停止します。最悪の場合、要素がそこにないため、要素がなくなるまで配列のサイズを半分にし続けます。これにはどのくらいかかりますか？ええと、配列を何度も半分に分割し続けるので、実行前に配列を O(log n) 回よりも多く半分に分割することはできないため、多くても O(log n) 回の繰り返しで完了します。配列要素が不足しています。
分割統治法(問題をバラバラに分割し、それらのピースを解決してから、問題を元に戻す)の一般的な手法に従うアルゴリズムは、これと同じ理由で対数項を持つ傾向があります。オブジェクトを分割し続けることはできません。 O(log n) 回の半分以上。この良い例として、マージソートを見たいと思うかもしれません。
10 進数の n は何桁ですか? 数字に k 桁がある場合、最大の桁は 10 kの倍数になります。k 桁の最大の数は 999...9 の k 倍であり、これは 10 k + 1 - 1に等しくなります。したがって、n に k 桁があることがわかっている場合、n の値は次のようになります。せいぜい 10 k + 1 - 1 です。k を n に関して解きたい場合は、次のようになります。
n ≤ 10 k+1 - 1
n + 1 ≤ 10 k+1
log 10 (n + 1) ≤ k + 1
(log 10 (n + 1)) - 1 ≤ k
ここから、k はおおよそ n の 10 を底とする対数であることがわかります。つまり、n の桁数は O(log n) です。
たとえば、大きすぎて機械語に収まらない 2 つの大きな数を加算する複雑さについて考えてみましょう。これらの数値が基数 10 で表されていると仮定し、その数値を m および n と呼びます。それらを追加する 1 つの方法は、小学校の方法を使用することです。数字を一度に 1 桁ずつ書き、右から左に作業します。たとえば、1337 と 2065 を足すには、次のように数字を書き出すことから始めます。
1 3 3 7
+ 2 0 6 5
==============
最後の桁を追加し、1 を運びます。
1
1 3 3 7
+ 2 0 6 5
==============
2
次に、最後から 2 番目 (「最後から 2 番目」) の数字を追加し、1 を繰り上げます。
1 1
1 3 3 7
+ 2 0 6 5
==============
0 2
次に、最後から 3 番目 ("最後から 2 番目") の数字を追加します。
1 1
1 3 3 7
+ 2 0 6 5
==============
4 0 2
最後に、最後から 4 番目の数字 ("preantepenultimate"... I love English) を追加します。
1 1
1 3 3 7
+ 2 0 6 5
==============
3 4 0 2
さて、私たちはどれだけの仕事をしたでしょうか？1 桁あたり合計 O(1) の作業 (つまり、一定量の作業) を行い、合計で O(max{log n, log m}) の桁を処理する必要があります。これにより、合計で O(max{log n, log m}) の複雑さが得られます。これは、2 つの数値の各桁にアクセスする必要があるためです。
多くのアルゴリズムは、ある基数で一度に 1 桁ずつ処理することで O(log n) 項を取得します。古典的な例は、一度に 1 桁ずつ整数をソートする基数ソートです。基数ソートにはさまざまな種類がありますが、通常は O(n log U) の時間で実行されます。ここで、U はソートされる最大の整数です。この理由は、ソートの各パスに O(n) の時間がかかり、ソートされる最大数の O(log U) 桁のそれぞれを処理するために合計 O(log U) の反復が必要になるためです。Gabow の最短パス アルゴリズムやFord-Fulkerson max-flow アルゴリズムのスケーリング バージョンなど、多くの高度なアルゴリズムは、一度に 1 桁ずつ処理するため、複雑さの中に対数項があります。
その問題をどのように解決するかについての 2 番目の質問については、より高度なアプリケーションを調査するこの関連する質問を参照することをお勧めします。ここで説明されている問題の一般的な構造を考えると、結果に対数項があることがわかっている場合は、問題をどのように考えるかについてより良い感覚を持つことができます。そのため、答えを与えるまでは答えを見ないことをお勧めします。ある考え。
お役に立てれば！
私たちがビッグオーの説明について話すとき、私たちは通常、与えられたサイズの問題を解決するのにかかる時間について話します。そして通常、単純な問題の場合、そのサイズは入力要素の数によって特徴付けられ、通常はnまたはNと呼ばれます（明らかに、常にそうであるとは限りません。グラフの問題は、頂点の数、V、およびエッジの数E。ただし、ここでは、オブジェクトのリストについて説明します。リストにはN個のオブジェクトが含まれます。）
問題は「大きい-ああ（Nのいくつかの関数）」であると言うのは、次の場合に限ります。
すべてのN>任意のN_0に対して、アルゴリズムの実行時間がその定数c倍 よりも短くなるような定数cがあります（Nの関数）。
言い換えれば、問題を設定するための「一定のオーバーヘッド」が重要である小さな問題について考えるのではなく、大きな問題について考えてください。そして、大きな問題について考えるとき、big-Oh of（Nの関数）は、実行時間が常にその関数の一定時間よりも短いことを意味します。いつも。
要するに、その関数は一定の係数までの上限です。
つまり、「log（n）のbig-Oh」は、「Nの一部の関数」が「log（n）」に置き換えられることを除いて、上記と同じ意味です。
それで、あなたの問題はあなたに二分探索について考えるようにあなたに告げます、それでそれについて考えましょう。たとえば、昇順で並べ替えられたN個の要素のリストがあるとします。そのリストに特定の番号が存在するかどうかを確認する必要があります。二分探索ではないことを行う1つの方法は、リストの各要素をスキャンして、それがターゲット番号であるかどうかを確認することです。あなたは幸運になり、最初の試みでそれを見つけるかもしれません。しかし、最悪の場合、N回チェックします。これは二分探索ではなく、大きくもありません。上記でスケッチした基準に強制する方法がないため、log（N）です。
その任意の定数をc=10に選択できます。リストに、N = 32の要素がある場合は、10 * log（32）= 50で、実行時の32よりも大きくなります。ただし、N=64の場合、10 * log（64）= 60、これは64の実行時間よりも短いです。c= 100、1000、または数億を選択できますが、それでもその要件に違反するNを見つけることができます。つまり、N_0はありません。
ただし、二分探索を行う場合は、真ん中の要素を選択して比較します。次に、半分の数を捨てて、それを何度も繰り返します。N = 32の場合、これは約5回しか実行できません。これは、log（32）です。N = 64の場合、これは約6回しか実行できません。これで、Nの値が大きい場合に要件が常に満たされるように、任意の定数cを選択 できます。
これらすべての背景から、O（log（N））が通常意味するのは、問題のサイズを半分に減らす簡単なことを行う方法があるということです。ちょうど二分探索が上で行っているように。問題を半分にカットしたら、何度も何度も何度も問題を半分にカットできます。しかし、重要なことに、実行できないのは、そのO（log（N））時間よりも長くかかる前処理ステップです。したがって、たとえば、O（log（N））時間内にそれを行う方法が見つからない限り、2つのリストを1つの大きなリストにシャッフルすることはできません。
（注：ほとんどの場合、Log（N）はlog-base-twoを意味します。これは、上記で想定したものです。）
次のソリューションでは、再帰呼び出しを含むすべての行が、X と Y のサブ配列の指定されたサイズの半分で実行されます。他の行は一定時間で実行されます。再帰関数は T(2n)=T(2n/2)+c=T(n)+c=O(lg(2n))=O(lgn) です。
MEDIAN(X, 1, n, Y, 1, n) から始めます。
MEDIAN(X, p, r, Y, i, k)
if X[r]<Y[i]
return X[r]
if Y[k]<X[p]
return Y[k]
q=floor((p+r)/2)
j=floor((i+k)/2)
if r-p+1 is even
if X[q+1]>Y[j] and Y[j+1]>X[q]
if X[q]>Y[j]
return X[q]
else
return Y[j]
if X[q+1]<Y[j-1]
return MEDIAN(X, q+1, r, Y, i, j)
else
return MEDIAN(X, p, q, Y, j+1, k)
else
if X[q]>Y[j] and Y[j+1]>X[q-1]
return Y[j]
if Y[j]>X[q] and X[q+1]>Y[j-1]
return X[q]
if X[q+1]<Y[j-1]
return MEDIAN(X, q, r, Y, i, j)
else
return MEDIAN(X, p, q, Y, j, k)
まだコメントできません...ネクロです！Avi Cohenの答えは間違っています。試してください：
X = 1 3 4 5 8
Y = 2 5 6 7 9
どの条件も真ではないため、MEDIAN(X, p, q, Y, j, k) は両方の 5 をカットします。これらは非減少シーケンスであり、すべての値が異なるわけではありません。
また、個別の値を使用して、次の偶数長の例を試してください。
X = 1 3 4 7
Y = 2 5 6 8
MEDIAN(X, p, q, Y, j+1, k) は 4 つをカットします。
代わりに、このアルゴリズムを提供し、MEDIAN(1,n,1,n) で呼び出します。
MEDIAN(startx, endx, starty, endy){
if (startx == endx)
return min(X[startx], y[starty])
odd = (startx + endx) % 2 //0 if even, 1 if odd
m = (startx+endx - odd)/2
n = (starty+endy - odd)/2
x = X[m]
y = Y[n]
if x == y
//then there are n-2{+1} total elements smaller than or equal to both x and y
//so this value is the nth smallest
//we have found the median.
return x
if (x < y)
//if we remove some numbers smaller then the median,
//and remove the same amount of numbers bigger than the median,
//the median will not change
//we know the elements before x are smaller than the median,
//and the elements after y are bigger than the median,
//so we discard these and continue the search:
return MEDIAN(m, endx, starty, n + 1 - odd)
else (x > y)
return MEDIAN(startx, m + 1 - odd, n, endy)
}