涉及一系列日志的Big-O证明

Question

证明

我把这个系列放到了总和中,但我不知道如何解决这个问题.任何帮助表示赞赏

Answer 1

有两个有用的数学事实可以帮到这里.首先,请注意任何x的⌈x⌉≤x+ 1.因此,

从i = 1到n的总和(⌈log(n/i)⌉)≤(从i = 1到n log(n/i)的总和)+ n

因此,如果我们可以证明第二个求和是O(n),那么我们就完成了.

使用日志属性,我们可以重写

log(n/1)+ log(n/2)+ ... + log(n/n)

= log(n ⁿ/n!)

让我们看看我们是否可以简化这一点.使用对数的属性,我们得到了

log(n ⁿ/n!)= log(n ⁿ) - log(n!)

= n log n - log(n!)

现在,我们可以使用斯特林的近似值,这就是说

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),如果需要的话.

希望这可以帮助!