big-o - O(log(n*log n) は O(log n) と見なすことができます

Question

f(n)=log(n*log n) を得たとします。O(log(n*log n)? または、log(n*log n)=log n + log(log n) を実行してから、関数 f(n) は O(log n) であると言う必要があります。 )?

Answer 1

まず第一に、あなたが観察したように：

 log(n*log n) = log(n)  + log(log(n))

ただし、log(log N) を N->large (Floris が示唆するように) と考えてください。

たとえば、N = 1000 とすると、log N = 3 (つまり、小さい数) となり、log(3) はさらに小さくなります。これは、N が巨大になる (つまり、コードが生成できる命令の数をはるかに超える) 場合にも当てはまります。

したがって、O(log(n * log n)) = O(log n + k) = O(log(n)) + k = O(log n)

これを別の方法で調べると、n * log n << n^2 となり、最悪の場合は次のようになります。

  O(log(n^2)) > O(log(n * log n))

したがって、2*O(log(n)) は上限であり、O(log(n * log n)) = O(log n)

Answer 2

定義を使用します。f(n) = O(log(n*log(n))) の場合、次のような正の定数 M と実数 n ₀が存在する必要があります。

|f(n)| ≤ M |log(n*log(n))|

すべての n > n _{0 に対して}。

_{ここで、(一般性を失うことなく) n 0} > 0と仮定しましょう。

ログ (n) ≥ ログ (ログ (n))

すべての n > n _{0 に対して}。

これから、次のことがわかります。

ログ (n (ログ (n)) = ログ (n) + ログ (ログ (n)) ≤ 2 * ログ (n)

代入すると、

|f(n)| ≤ 2*M|log(n))| すべての n > n _{0 に対して}

2*M も正の定数なので、すぐに f(n) = O(log(n)) となります。