java - 不重置的嵌套 While 循环的运行时间

Question

下面的代码是 O(n^2) 还是 O(n)？

int i=0, j=0;
while (i < n) {
  while (j < n) {
    j++;
  }
  i++;
}

由于内部 while 循环只从 0 到 n 运行一次，我想这相当于有两个单独的 while 循环，因此总运行时间为 O(2n)。

Answer 1

在这段特定的代码中是 O(n)。例如如果 n=10 for i=0 内部循环从 j=0 执行到 j=9(10 次)并且 for i = 1 到 9 内部循环执行 0 次，(因为 j(10) >n(10) 永远不会变为真)，所以总时间 = 10 次外部 + 10 次内部 = 20= 2n因此时间复杂度为 O(n)