求证log(log(n))∈O(log(n))：常数C的取值疑问

嘿，你的核心思路没问题，只是需要补全一些符合大O符号严谨定义的细节，我来一步步帮你理清楚：

先明确大O的核心规则 #

首先得回忆清楚：我们说 $f(n) = O(h(n))$，当且仅当存在正常数 $C$ 和 $n_0$，使得对所有 $n \geq n_0$，都有 $|f(n)| \leq C \cdot |h(n)|$。这是我们推导的依据。

补全你的推导逻辑 #

我们以自然对数（$\ln$）为例，换成常用对数（$\log_{10}$）逻辑完全一致：

• 首先，$\log(\log(n))$ 有意义的前提是 $\log(n) > 0$，也就是 $n > 1$；但要让这个函数值为正，得满足 $\log(n) > 1$，也就是 $n > e$（约2.718）。
• 你提到的 $\log(\log(n)) < \log(n)$ 这个不等式是对的，但要明确适用范围：当 $\log(n) > 1$（即 $n > e$）时，因为对于任意 $x > 1$，都有 $\log(x) < x$，这里令 $x = \log(n)$，代入就得到这个结论。

确定符合要求的常数 $C$ 和 $n_0$ #

根据大O的定义，我们可以直接选：

• $C = 1$
• $n_0 = e^e \approx 15.154$（或者取整数16，更方便实际验证）

这样一来，对于所有 $n \geq 16$，$\log(\log(n))$ 肯定小于等于 $\log(n)$，完全满足 $|g(n)| \leq C \cdot \log(n)$ 的要求。

如果是常用对数的话，$n_0$ 就是 $10^{10}$，$C$ 同样取1，逻辑完全一样。

额外小补充 #

其实当 $n$ 在 $(e, e^e)$ 之间时，$\log(\log(n))$ 是小于1的正数，而 $\log(n)$ 大于1，所以 $\log(\log(n)) < \log(n)$ 依然成立，所以 $n_0$ 取 $e$ 也没问题，但取 $e^e$ 是为了让两边都是大于1的正数，看起来更直观。

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