25

私は現在アルゴリズム分析について読んでおり、特定のアルゴリズム（パス圧縮を使用した加重クイックユニオン）はN + M lg * Nのオーダーであると読みました。これは線形ですが、lg*Nはこのユニバースでは定数であるためです。ここでは、どのような数学演算が参照されていますか。lg*Nという表記に慣れていません。

4

6 に答える 6

38

これまでのところ、ここでの答えは間違っています。lg* n（「ログスター」と読みます）は反復対数です。これは、再帰的に次のように定義されます。

         0             if n <= 1
lg* n =
         1 + lg*(lg n) if n > 1

別の見方をすれば、結果が1以下になるまでに対数を反復しなければならない回数です。

それは非常にゆっくりと成長します。分析でポップアップするアルゴリズムのいくつかの例を含むウィキペディアで詳細を読むことができます。lg* n

于 2011-03-06T19:10:09.087 に答える
0

この講義のスライド44で分析されたアルゴリズムについて話していると仮定します： http ：//www.cs.princeton.edu/courses/archive/fall05/cos226/lectures/union-find.pdf

彼らが「lg*Nはこの宇宙では定数である」と言うところ、私は彼らが完全に文字通りではないと信じています。スライドの右側にある表のように、lg*NはNとともに増加するように見えます。たまたま非常に遅い速度で成長するため、他の方法とは考えられません（N = 2 ^ 65536-> log * n = 5）。そのため、問題を引き起こすほど大きくなることはないため、log*Nを定数として無視できると言われているようです。

しかし、私は間違っている可能性があります。それは私がそれを読む方法です。

編集：この方程式では、「lg *N」を2^（lg *（N-1））と定義していることに注意してください。たとえば、N値が2 ^（2 ^（65536））[はるかに大きい数]の場合、lg * N=6になります。

于 2011-03-06T19:01:29.853 に答える
0

Jasonによるlg*nの再帰的定義は、 2 II m <= n <2 II（m + 1）の場合、 lg * n = mと同等です 。ここで、2 II m = 2 ^ 2 ^ ... ^ 2（繰り返しのべき乗、 2）のmコピー は、クヌースの二重上矢印表記です。したがって、lg * 2 = 1、lg * 2 ^ 2 = 2、lg * 2 ^ {2 ^ 2} = 3、lg * 2 ^ {2 ^ {2 ^ 2}} = 4、lg * 2 ^ {2 ^ {2 ^ {2 ^ 2}}} =5。 したがって、 2 ^ {16} <= n <2^{65536}の場合はlg*n=4です。関数lg*nは非常にゆっくりと無限大に近づきます。（ n-2の上向き矢印を含むアッカーマン関数A（n、n）の逆関数よりも高速です。）



スティーブン

于 2013-04-24T06:03:34.727 に答える
-4

対数はlogまたはlgで表されます。あなたの場合、正しい解釈はN + M * log（N）だと思います。

編集：漸近的複雑性分析を行う場合、対数の底は重要ではありません。

于 2011-03-06T18:55:31.537 に答える
-4

lgは「LOG」または逆指数です。lgは通常2進数を指しますが、アルゴリズム分析の場合、2進数は通常重要ではありません。

于 2011-03-06T18:56:03.623 に答える
-4

lgnは対数基数nを指します。これは、方程式2 ^ x=nに対する答えです。Big Oの複雑さの分析では、ログに記録するベースは関係ありません。CSでは2の累乗が発生するため、ベースを選択する必要がある場合でも、ベース2になります。

それが発生する場所の良い例は、2^h-1ノードを持つ高さhの完全な二分木です。nをノードの数とすると、この関係は、ツリーが高さlg nで、ノードがn個あるということです。このツリーをトラバースするアルゴリズムは、値がツリーに格納されているかどうかを確認するために最大でlgnかかります。

予想通り、ウィキには素晴らしい追加情報があります。

于 2011-03-06T19:00:49.180 に答える