質問

Big-Oの知識が乏しく、対数項が式に出てくると余計に混乱してしまいます。

誰かが私に簡単な言葉で説明してくれるでしょうか。 O(log n) アルゴリズムは何ですか？対数はどこから来るのでしょうか？

これは特にこの中間練習問題を解こうとしたときに出てきたものです。

X(1..n) と Y(1..n) に、それぞれ非減少順に並べられた2つの整数のリストがあるとする。2n個の要素を組み合わせたときの中央値（またはn番目に小さい整数）を求めるO(log n)時間のアルゴリズムを与えよ。 例えば、X = (4, 5, 7, 8, 9)とY = (3, 5, 8, 9, 10)の場合、7は(3, 4, 5, 5, 7, 8, 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つのステップで終了することに注意してください。 興味深いことに、私たちはまた、そのログ ₂ 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つのステップを要し、ログ <サブ 2 128 = 7です。これは偶然でしょうか？ いや！そうではない。 これにはちゃんとした理由があるのです。 ある数nを2でi回割ったとする。 すると、数n / 2が得られる。 ⁱ . この値が最大でも1であるiの値を解きたい場合は、次のようになります。

n / 2 ⁱ ≤ 1

n ≤ 2 ⁱ

ログ ₂ n ≦ i

つまり、i≧logとなるような整数iを選ぶと ₂ となるような整数 i を選ぶと、n を i 回半分に割った後、最大でも 1 の値が得られます。これが保証される最小の i は、およそ log ₂ nであるため、数が十分に小さくなるまで2で割るアルゴリズムがあれば、それはO（log n）ステップで終了すると言うことができます。

重要なのは、n をどのような定数で割っても (それが 1 より大きい限り)、問題にはならないということです。定数 k で割る場合、log _k nステップで1に到達します。 したがって、入力サイズをある分数で繰り返し割るようなアルゴリズムは、終了するために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) 回以上半分に切り続けることはできないからです。 あなたは マージ ソート をその好例として挙げることができます。

値を1桁ずつ処理する

10進数のnは何桁でしょう？ もしk桁の数字があれば、最大の桁は10の何倍かになります。 ^k . 最大のk桁の数字は999...9のk倍であり、これは10に等しい。 ^{k + 1} - その結果，n が k 桁であることがわかれば，n の値は最大でも 10 ^{k + 1} - 1であることがわかる。もし、nの項でkを解きたいなら、次のようになる。

n ≤ 10 ^k+1 - 1

n + 1 ≤ 10 ^k+1

ログ <サブ 10 (n + 1) ≤ k + 1

(ログ <サブ 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番目の桁（"penultimate"）を追加して、1を運びます。

       1  1
    1  3  3  7
+   2  0  6  5
==============
          0  2

次に、最後から3番目の桁（"antepenultimate"）を追加します。

       1  1
    1  3  3  7
+   2  0  6  5
==============
       4  0  2

最後に、4桁目から最後（quot;preantepenultimate"...英語大好き）までの数字を追加します。

       1  1
    1  3  3  7
+   2  0  6  5
==============
    3  4  0  2

さて、どれだけの作業をしたでしょうか？ 1桁あたり合計O(1)の仕事（つまり、一定量の仕事）をし、処理する必要がある桁数は合計O(max{log n, log m})です。 これは、2つの数字の各桁を訪問する必要があるため、合計でO(max{log n, log m})の複雑さになります。

多くのアルゴリズムが、あるベースで一度に1桁ずつ処理することから、O(log n)の項を得ます。 古典的な例としては 基数ソート これは整数を一度に一桁ずつソートします。 基数ソートには多くの種類がありますが、通常 O(n log U) の時間で実行されます（U はソートされる最大の整数）。 この理由は、ソートの各パスにO(n)回の時間がかかり、ソートされる最大数のO(log U)桁をそれぞれ処理するために、合計O(log U)回の繰り返しが必要となるからです。 多くの高度なアルゴリズム、例えば Gabowの最短経路アルゴリズム や、スケーリング版の フォード・フルカーソン最大流アルゴリズム は、一度に 1 桁ずつ処理するため、その複雑さは対数項となります。

その問題をどのように解決するかという2つ目の質問については この関連質問 で、より高度な応用を探っています。 ここで説明されている問題の一般的な構造を考えると、結果に対数項があることがわかっているときに、どのように問題を考えればよいのかがわかると思いますので、少し考えてから答えを見るようにすることをお勧めします。

お役に立てれば幸いです。