（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)？

   是

2. 是不是也h= O(log n)？

   否

证明：

使用正式定义：

F（N）= O（G（N））指有正常数c和n0，使得对于所有n≥n0，0≤f（n）≤cg（n）。函数f的c和n0的值必须是固定的，并且不能取决于n。

1. f = O(logn) <=> (log n)/ (log(log n)) = O(logn)

   所以，你需要找到c和n0这样0 ≤ (log n)/ (log(log n)) ≤ c*logn所有n ≥ n0。假设对数基数为b（实际上并不重要，但您可以在{2,e,10}中考虑b）。如果您选择c=1和n0=b^b^2，0 ≤ (log n)/ (log(log n)) ≤ logn适用于所有n ≥ b^b^2。

   • 第一部分是真实的，因为log n ≥ log b^b^2 = b^2 ≥ 0和log(log n) ≥ log(log b^b^2) = 2 ≥ 0
   • 第二部分也是如此，因为它变得log(log n) ≥ 1和log(log n) ≥ log(b^2) = 2 ≥ 1。

2. 类似于第一个证明，你需要证明你不能选择c和n0，使(log n) * (log(log n)) ≤ c*logn是所有n ≥ n0如此。并且对于大的n它变为(log(log n)) ≤ c，因为log n不能是0。很明显，你不能选择c，因为n > b^b^c不会是真​​的。