c - j+=i 的 O 表示法

Question

我需要找到以下代码的 O 表示法:

for(i = 0; i < N; i++){
  for(j = 0; j < N; j+=i){
    x+=y;
  }
}

我已经能够将它降低到 O(N*log(N))，但我想确定。
这种函数有我可以查找和研究的名称吗？

Answer 1

你的代码是 O(∞)。在第一个外层循环中，i 为 0，这意味着您对 j 的增量为 0，因此当 N > 0< 时，内层循环变为无限循环.