关于logn/loglogn与loglogn的大O时间复杂度判定咨询

问题1：$\log n / \log\log n$ 是否属于 $O(\log(n - \log n))$？ #

是的。通过渐近分析和大O定义可验证：

• 先简化 $\log(n - \log n)$：
  $$\log(n - \log n) = \log\left(n\left(1 - \frac{\log n}{n}\right)\right) = \log n + \log\left(1 - \frac{\log n}{n}\right)$$
  当 $n$ 足够大时，$\frac{\log n}{n}$ 趋近于0，$\log\left(1 - \frac{\log n}{n}\right)$ 相对于 $\log n$ 可忽略，因此 $\log(n - \log n)$ 和 $\log n$ 渐近同阶。
• 当 $n \geq e^e \approx 15.15$ 时，$\log\log n \geq 1$，此时 $\frac{\log n}{\log\log n} \leq \log n$。
• 根据大O定义，取 $c=1$、$n_0=16$，当 $n \geq n_0$ 时，$\frac{\log n}{\log\log n} \leq 1 \cdot \log(n - \log n)$，满足条件。因此 $\log n / \log\log n \in O(\log(n - \log n))$。

问题2：$\log\log n$ 是否属于 $O(\log(n / \log n))$？ #

是的。同样通过渐近分析和定义验证：

• 先简化 $\log(n / \log n) = \log n - \log\log n$，当 $n$ 足够大时，$\log n$ 远大于 $\log\log n$，$\log(n / \log n)$ 与 $\log n$ 渐近同阶。
• 我们需要找到 $c>0$ 和 $n_0$，使得 $n \geq n_0$ 时，$\log\log n \leq c \cdot (\log n - \log\log n)$。整理得 $1 \leq c \cdot \left(\frac{\log n}{\log\log n} - 1\right)$，当 $n$ 足够大时，$\frac{\log n}{\log\log n}$ 趋向无穷大。
• 取 $c=1$、$n_0=1000$，此时 $\log 1000 \approx 9.96$，$\log\log 1000 \approx 2.3$，显然 $9.96 \geq 2 \times 2.3$，满足 $\frac{\log n}{\log\log n} - 1 \geq 1$。因此 $\log\log n \leq \log(n / \log n)$，故 $\log\log n \in O(\log(n / \log n))$。

内容的提问来源于stack exchange，提问作者Lilo