内循环根据外循环增加的时间复杂度

Question

我必须找出下面代码的时间复杂度。但是随着 j 根据 i 的值增加而感到困惑。

否则我认为它会是 $O(n^2)$。

#include <iostream> 
using namespace std; 
for(int i=0;i<n;i++) 
    { 
      for(int j=0;j<n;j+=i) 
      { 
        //Some O(1) Code 
      } 
    }

Answer 1

没有为此函数定义时间复杂度，因为它不会在所有输入上终止。事实上，它只在 n <= 0 时终止。

Answer 2

正如其他人所说，假设 $n > 0$ 那么在外循环的第一次迭代中，内循环的增量为 0 并且永不终止。

如果您的意思是让内部循环递增 i+1，则迭代总数为：

Link to latex: I don't have enough reputation to embed images.

其中H_n为n次谐波数

所以复杂度为 O(n log n)。

内循环根据外循环增加的时间复杂度

Time complexity where inner loop increases according to outer loop

time-complexity