（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不會是真​​的。