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)
• 从两侧删除一个“log”，结果为 O((log n)²) = O(log n)。<

这有效吗？

Answer 1

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

O(log n¹³⁷)

= O(137 log n)

= O(log n).

因此，从两侧删除日志可以得到 O(n¹³⁷) = O(n)。

但是，当然，这是不对的。原因是，虽然情况是如果 f(n) = O(g(n)) then 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)) 的情况都不是这样。