内循环是如何执行"n/i"次的？

Question

我对代码片段的时间复杂度有疑问，并且不太理解给出的解决方案。

function (n) {
           for(int i =0 ; i < n ; i ++){
                       for(int j = 0 ; j <= n ; j += i){
                                  printf("*");
                                      }

在上面的代码中，假设内循环对 i 的每个值执行 n/i 次。并且，整体时间复杂度为O(nlogn)。

我想不通为什么内循环执行了 n/i 次。有人可以帮帮我吗。

Answer 1

有两个循环，一个递增i，一个递增j。

给定固定 i，对于 j 循环的每一次传递，j 递增 i，直到 j 达到 n .

所以每次迭代中j的值为：

j
j + i
j + 2i
...
j + (n/i - j/i)i 

如您所见，这运行了 O(n/i) 次。