algorithm - 対数に関する Big-O 表記法

Question

いくつかの対数関数の Big-O 表記を識別してほしいというインタビューの質問を受けました。機能は次のとおりです。

f(x) = ログ⁵ (x)

f(x) = log(x ⁵ )

f(x) = log(6*log x)

f(x) = ログ (ログ x)

1 番目と 2 番目の Big-O は等価ではなく、3 番目と 4 番目も等価ではないと言われました。なぜそれらが同等ではないのか、また Big-O とは何なのかを説明できる人はいますか?

Answer 1

1. log ⁵ x は log log log log log log x を書くのと同じで、これはx の成長が非常に遅い関数です。
2. これは 5 log x (対数の内側のべき乗を外側の乗算に書き換える) に相当し、これは log x に相当します。
3. これは、log 6 + log log x に相当し、log log x に相当します。
4. これは単なる log log x です。

したがって、O(log log log log log x)、O(log x)、O(log log x)、O(log log x) という 3 つの異なる Big-O クラスがあります。

面接官が 3 と 4 が違うと言った場合は、彼が間違っているか、あなたが質問を覚えていないかのどちらかです (常に起こります)。

Answer 2

これは数学の問題です:

1. f(x) = ログ⁵ (x)
2. f(x) = log(x ⁵ ) = 5 * ログ x
3. f(x) = ログ (6*ログ x) = ログ 6 + ログ (ログ x)
4. f(x) = ログ (ログ x)

だからビッグオーは

1. O(ログ⁵ (x))
2. O(log x)
3. O(ログ (ログ x))
4. O(ログ (ログ x))

したがって、(1) と (2) は同等ではありませんが、(3) と (4) は同等です (ただし、(1) と (2) の両方とは異なります)。

Answer 3

f(x) = log^5(n)
f(x) = log(n^5) -> 5 log(n)
O(5 log(n)) < O(log(n)^5)

f(x) = log(6*log n) -> log(6)+log(log(n))
f(x) = log(log n) 
log(log n) < log(6) + log(log(n)) 

、ただし、log(6) は定数であるため、同じ O を持ちます

Answer 4

f(n)ではなく、という意味だと思いますf(x)。1 と 2 の場合、は、 whilelog^5(n)と同等です。O(log log log log log(n))log(n^5) = 5 log(n) = O(log n)

3と4については、私は同意しません。log(6*log n) = log(6) + log(log n) = O(log log n)、これは 4 - と同じO(log log n)です。