涉及日志总和的 Big-O 证明
Big-O proof involving a sum of logs
证明
我把级数放到了求和中，但我不知道如何解决这个问题。感谢任何帮助
这里有两个有用的数学事实可以提供帮助。首先，请注意对于任何 x，⌈x⌉ ≤ x + 1。因此，
sum from i = 1 to n (⌈log (n/i)⌉) ≤ (sum from i = 1 to n log (n / i)) + n
因此，如果我们能证明第二个求和是 O(n)，我们就完成了。
利用日志的属性，我们可以重写
log(n/1) + log(n/2) + ... + log(n/n)
= log(nn / n!)
让我们看看是否可以简化它。使用对数的性质，我们得到
log(nn / n!) = log(nn) - log(n!)
= n log n - log (n!)
现在，我们可以使用 Stirling 的近似值，即
log (n!) = n log n - n + O(log n)
因此：
n log n - log (n!)
= n log n - n log n + n - O(log n)
= O(n)
因此求和为 O(n)，按要求计算。
希望对您有所帮助！
通常我们知道：
因此：
证明
我把级数放到了求和中，但我不知道如何解决这个问题。感谢任何帮助
这里有两个有用的数学事实可以提供帮助。首先，请注意对于任何 x，⌈x⌉ ≤ x + 1。因此，
sum from i = 1 to n (⌈log (n/i)⌉) ≤ (sum from i = 1 to n log (n / i)) + n
因此，如果我们能证明第二个求和是 O(n)，我们就完成了。
利用日志的属性，我们可以重写
log(n/1) + log(n/2) + ... + log(n/n)
= log(nn / n!)
让我们看看是否可以简化它。使用对数的性质，我们得到
log(nn / n!) = log(nn) - log(n!)
= n log n - log (n!)
现在，我们可以使用 Stirling 的近似值，即
log (n!) = n log n - n + O(log n)
因此：
n log n - log (n!)
= n log n - n log n + n - O(log n)
= O(n)
因此求和为 O(n)，按要求计算。
希望对您有所帮助！
通常我们知道：
因此：