(log n)/ (log(log n))的顺序是什么？

Question

f=(log n)/ (log(log n))的顺序是什么？

是f= O(log n)吗？为什么会这样呢？

h=(log n) * (log log n)的顺序是什么？

它也是h= O(log n)吗？为什么这是正确的？

Answer 1

1. 是f= O(log n)

是

1. 它也是h= O(log n)吗

不是

证明：

使用形式定义

f(n) = O(g(n))是指存在正常数c和n0，使得0≤f(n)≤cg(n)为n≥n0。对于函数f，c和n0的值必须是固定的，不能依赖于n。

1. f = O(logn) <=> (log n)/ (log(log n)) = O(logn) 因此，您需要找到c和n0，以便为所有n ≥ n0找到0 ≤ (log n)/ (log(log n)) ≤ c*logn。假设对数基数是b (实际上并不重要，但您可以在{2,e,10}中考虑b )。如果您选择c=1和n0=b^b^2，则为所有n ≥ b^b^2选择0 ≤ (log n)/ (log(log n)) ≤ logn。

- the first part is true, because `log n ≥ log b^b^2 = b^2 ≥ 0` and `log(log n) ≥ log(log b^b^2) = 2 ≥ 0`
- the second part is also true, because it becomes `log(log n) ≥ 1` and `log(log n) ≥ log(b^2) = 2 ≥ 1`.

​

1. 类似于第一个证明，您需要证明不能选择c和n0，这样(log n) * (log(log n)) ≤ c*logn对于所有n ≥ n0都是正确的。对于一个大的n，它变成了(log(log n)) ≤ c，因为log n不能是0。很明显，您不能选择一个c，因为它对n > b^b^c不适用。