两个系列有什么区别？
What is difference between two series?
我正在研究渐近时间复杂度的概念并遇到了两个系列：
n + n/2 + n/3 + n/4 + ....... + n/n //yields O(nlogn)
n + n/2 + n/4 + ....... + 1 //yields O(n)
这两个数列的计算方式究竟有什么不同b/w？
我认为是关于 convergent 和 divergent 系列。第一个提到的是 divergent harmonic progression 而第二个是 convergent geometric progression
convergent geometric series 的总和等于
S = n / (1−r)。因此我相信 O(n) 时间复杂度
divergent harmonic progression 就是 SUM(1,n)(1/x) * n
我们知道，
Integration(1, n)(1/x dx) = ln(n),
Integration(1, n)(1/x dx) = ln(n) <= SUM(1,n)(1/x)
具有 O(logn) 的复杂性。对于我们的案例，乘以 n，因此有 O(nlogn)
我正在研究渐近时间复杂度的概念并遇到了两个系列：
n + n/2 + n/3 + n/4 + ....... + n/n //yields O(nlogn)n + n/2 + n/4 + ....... + 1 //yields O(n)
这两个数列的计算方式究竟有什么不同b/w？
我认为是关于 convergent 和 divergent 系列。第一个提到的是 divergent harmonic progression 而第二个是 convergent geometric progression
convergent geometric series 的总和等于
S = n / (1−r)。因此我相信 O(n) 时间复杂度
divergent harmonic progression 就是 SUM(1,n)(1/x) * n
我们知道，
Integration(1, n)(1/x dx) = ln(n),
Integration(1, n)(1/x dx) = ln(n) <= SUM(1,n)(1/x)
具有 O(logn) 的复杂性。对于我们的案例，乘以 n，因此有 O(nlogn)