給出一個簡單的函數，使得和S（n）是O（f（n））？

Question

一直呆在這個傢伙。

考慮總和S（n）=ΣLog（i）。給一個簡單函數f（n），使得和S（n）爲O（f（n））。解釋爲什麼。

（西格瑪開始於我= 1，以n結束）

我該怎麼辦呢？請一步一步解釋。

Answer 1

任何函數g（n）都可以使用上面的Log（n）。事實上，Log（n）= O（g（n））意味着S（n）= O（f（n）），其中f（n）=Σg（i）。例如g（n）= n使用三角形公式來建立S（n）= 0（n 2）。

如果你想要一個緊密的邊界，你可以注意到ΣLog（i）= Log（n！），並使用Stirling formula。

如果您不允許使用斯特林公式，請取Lg（i）（以2爲底的對數）的上限之和。它們遵循規則模式，從1： 0,1,2,2,3,3,3,4,4,4,4,4,4,4,5,5,5,5 ，5，5，5，5，5，5，5，5，...，5，5，...，

每次運行的長度加倍，以便與n的總和不超過Lg（n）不同運行，總和由n.ceiling（Lg（n）+1）限定。

推理對於自然對數是有效的，因爲所有的對數都是成比例的：Log（i）= Lg（i）/ Lg（2）。

ΣLog（i）= O（n.Log（n））。

Answer 2

只是因爲log是單調的：

sum[i=1..n]log(i) <= sum[i=1..n]log(n) = n*log(n)

所以這是O(n*log(n))

，並確認，我們不能提高這一上限：

sum[i=1..n]log(i) >= sum[i=n/2..n]log(i) >= sum[i=n/2..n]log(n/2) = (n/2)*log(n/2)

所以這是Omega(n*log(n))

Answer 3

看看這個link。

@Yves Daoust釘的總和值。簡而言之（當n = 16且base = 2時）：

0 + 1 + 2 + 2 + 3 + 3 + 3 + 3 + 4 + 4 + 4 + 4 + 4 + 4 + 4 + 4 = 1 +（2 * 2）+（4 * 3）+（8 * 4）。

使用base> = 3進行測試以更清晰地查看圖案（瞭解上面的封閉表格）。