algorithm - 关于 O((log n)²) 与 O(log n) 的混淆

Question

我在互联网上找不到任何好的解释 O((log  n ) ² ) 等于的东西。我认为它等于 O(log  n )，通过以下论点：

• O(log (log  n ) ² )
  = O(log (log  n  · log  n ))
  = O(log log  n  + log log  n )
  = O(2 log log  n )
  = O(log log  n )
• 从两侧删除“日志”给出 O((log  n ) ² ) = O(log  n )。

那有效吗？

标签： algorithmmathbig-ologarithm

Answer 1

你在这里提出的论点是一个有趣的论点，但不幸的是它不起作用。要了解原因，让我们“证明”O(n ¹³⁷ ) = O(n)。为此，请注意

O(log n ¹³⁷ )

= O(137 日志 n)

= O(log n)。

所以从两边删除日志给了我们 O(n ¹³⁷ ) = O(n)。

但当然，这是不对的。原因是，如果 f(n) = O(g(n)) 然后 log n = O(log g(n))，通常情况下 log f(n) = O (log g(n)) 意味着 f(n) = O(g(n))。

至于您最初的问题- log ² n = O(log n) 的情况并非如此。事实上，对于任何不是 O(1) 的函数 f，情况都不是 f(n) ² = O(f(n))。