2

この質問は、並べ替えや検索などのログインの問題の出現につながるソリューション間に抽象的な類似性があるかどうかに関するものです。または、もっと簡単に言えば、アルゴリズムの複雑さの中でログが頻繁に現れるのはなぜでしょうか?

4

3 に答える 3

6

対数は、問題が倍数係数によってサイズを繰り返し縮小できる場合によく現れます。定義により、問題を一定のサイズ (サイズ 1 など) に縮小するには、対数のステップ数が必要です。

典型的な例は、二分探索で行われるように、データセットの半分を繰り返し削除することです。これはO(log2(n))複雑さを与えます。一部の並べ替えアルゴリズムは、データセットを繰り返し半分に分割することで機能するため、時間計算量に対数項があります。

より一般的には、対数は分割統治の再帰関係の解によく現れます。詳細については、ウィキペディアのマスター定理を参照してください。

于 2014-10-15T19:40:37.153 に答える
0

logは、ブール論理のため、コンピューター サイエンスで非常に頻繁に使用されます。すべてはtrue 対 falseまたは1 対 0またはto be または not to beに還元できます。ifステートメントがある場合は 1 つのオプションがあり、そうでない場合は他のオプションがあります。これは、ビット (0 または 1) または影響の大きい問題に適用できますが、決定事項があります。現実の世界と同じように、決断を下すとき、別の決断をしていたら起こりえたであろう問題については気にしません。これが、ログ2 (n)が非常に頻繁に表示される理由です。

次に、より複雑なすべての状況 (例: 3 つの状態から 1 つの可能な状態を選択する) をlog 2 (n)に減らすことができます=> 対数の底は問題ではありません (定数は関数の傾向に影響しません。同じ次数を持っています ):

  • 数学的証明:

              loga(y)      1
logx(y) = ------- = -------- * loga(y) = constant * loga(y)
          loga(x)    loga(x)

  • プログラマー向けの証明:

    switch(a) { 
    case 1: ... ;
    case 2: ... ;
    ...
    default: ... ;
}

    と類似しています：

    if (a == 1) {  
    ...
} else {
    if ( a == 2 ) {
        ...
    }
    ...
}

    (オプションの aswitchはステートメントkと同等です。 where = constant )k-1 if-elsek

しかし、なぜログに記録するのですか? 指数の逆だからです。最初の決定で、大きな問題を 2 つの部分に分けます。次に、「良い」半分だけを 2 つの部分に分けます。

n      = n/2^0         // step 1
n/2    = n/2^1         // step 2
n/4    = n/2^2         // step 3
n/8    = n/2^3         // step 4
...
n/2^i  = n/2^i         // step i+1

Q：何段あるの？

A : i+1 (0 から i まで)

必要な要素が見つかったときに停止するため (他に決定できることはありません) => n = 2^i. 底が 2 の対数を適用すると、次のようになります。

log2(n) = log2(2^i)
log2(n) = i
=> i + 1 = log2(n) + 1

しかし、定数は複雑さに影響しません => log 2 (n) steps です。

于 2014-10-15T19:45:52.360 に答える
0

ログは、アルゴリズムの複雑さ、特に再帰アルゴリズムで多く表示されます..

たとえば、バイナリ検索を見てみましょう。

100 要素のソートされた配列 A があり、数値 15 を探しています。

二分探索では、中央の要素 (50) を見て、それを 15 と比較します。要素が 15 より大きい場合は、50 と 100 の間の中央の要素を見つけます。これは 75 です。もう一度比較します。15 が75の要素よりも大きい場合、要素87である75と100の間の要素を調べます...要素が見つかるまで、または中間の数字がなくなるまでこれを続けます...

中間の数をチェックするこの方法を実行するたびに、検索するために残っている要素の総数が半分になります。

したがって、最初のパスは O(n/2) の複雑さを与えます..次のパスは O(n/4)... O(n/8) などです..このパターンを表すためにログを使用します..

対数ベースになるアルゴリズムの各パスで検索する要素の数を半分に削減しているため、バイナリ検索は O(log2(n)) の複雑さをもたらします

ほとんどのアルゴリズムは、元のデータを別々の部分に分割して解決することにより、操作の数をできるだけ少なくしようとします。これが、ログが頻繁に表示される理由です。

于 2014-10-15T19:51:44.250 に答える