logn/loglogn的时间复杂度

Question

logn/loglogn

的时间复杂度是

O(log(n-logn))

吗？

还有

loglogn=O(log(n/logn))

呢？

我试图通过定义来证明两者，但我找不到有效的 n0,c 。 我也尝试过计算两个函数的极限，但没有达到 inf/0。

Answer 1

听起来像是家庭作业问题，但3个月后可能已经逾期了，所以我给出参考答案。

在这种情况下，人们可以在保留声明的同时寻找更容易比较的替代。

• n-log n > n/2

  n 足够大。所以在 big-o 中我们得到

  O(log(n/2)) = O(log n)

  是

  O(log(n-log n))

  的子集。现在很容易看出

  log n / log log n

  位于

  O(log n)

  中，因此也在

  O(log(n-log n))

  中。
• 同样的技巧适用于问题的第二部分

  log n < n/log n