n が大きくなると、log*(log n) と log(log* n) の 2 つの関数のほうが速くなりますか?
ここで、log* 関数は反復対数であり、次のように定義されています。
書き方が違うだけで同じだと思いますが、違いはありますか？
質問する
3497 次
1 に答える
16
log* n は反復対数であり、n が大きい場合は次のように定義されます。
log* n = 1 + log*(log n)
したがって、log*(log n) = (log* n) - 1 です。log* は、ある固定定数 (通常は 1) に達する前に値に log を適用する必要がある回数であるためです。最初に別のログを作成すると、プロセスから 1 つのステップが削除されます。
したがって、log(log* n) は、log* (log n) = log* n - 1 よりもはるかに小さくなります。これは、適度に大きな x の場合、log x < x - 1 であるためです。
これを理解するためのもう 1 つのより直感的な方法: log* 関数は、log 関数よりも大きな数値を圧縮するのにはるかに優れています。したがって、大きな数を小さくしたい場合は、最初に log* n を計算して n を可能な限り縮小し、次にその上で log (log (log* n)) を使用すると、効率が大幅に向上します。残っているものを引き下げる。
お役に立てれば！
于 2013-10-04T03:15:42.080 に答える