两个嵌套循环的复杂性，内部循环步进依赖于外部循环变量
Complexity of two nested loops with the inner loops stepping dependend on the outer loops variable
function(n) {
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j+=i)
printf("*");
}
我以为这是 O(n²logn)，但书上说是 O(n*log(n))，所以我哪里错了？
对于 i 的每个值，内部循环执行 (n-1)/i+1 次，因为 for each i the inner loop executes according to following equation which satisfies an AP ie.. 1+(x-1)*i=n which implies x = (n-1)/i + 1
显然是要组成AP了。所以现在您所要做的就是对 1<=i<=n 的表达式求和。
即
((n-1)/1 +1) + ((n-1)/2+1)+ ((n-1)/3+1) //upto n because max value of i can be n
that becomes n + Summation((n-1)/i) where i can go upto n.
评估复杂度为 O(nlogn)
function(n) {
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j+=i)
printf("*");
}
我以为这是 O(n²logn)，但书上说是 O(n*log(n))，所以我哪里错了？
对于 i 的每个值，内部循环执行 (n-1)/i+1 次，因为 for each i the inner loop executes according to following equation which satisfies an AP ie.. 1+(x-1)*i=n which implies x = (n-1)/i + 1
显然是要组成AP了。所以现在您所要做的就是对 1<=i<=n 的表达式求和。 即
((n-1)/1 +1) + ((n-1)/2+1)+ ((n-1)/3+1) //upto n because max value of i can be n
that becomes n + Summation((n-1)/i) where i can go upto n.
评估复杂度为 O(nlogn)