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,这意味着您的增量为j0,因此内部循环变为无限循环N > 0.

Answer 2

对于从0开始的情况:

你的代码是O(∞),正如ShadowRanger的答案所解释的那样.

对于从1开始的情况:

您可以简单地使用观察结果,即您的实际复杂度f(N)受以下因素限制:

f(N) <= N/1 + N/2 + N/3 + ... + N/N 

     <= N * (Bound of value of Harmonic Number) 

     < c1 * N * ( log (N) ) i.e. O( N log(N) )

要证明谐波数的值O( log(N) ),您可以使用简单的微积分.请参考此处和此处.