带有嵌套的for-loop时间复杂度分析的小细节误解...如何区分O（n）和O（n²）

Question

对于以下算法：

 int x = 0;
 for (int i = 0; i < n; i++)
     for (j = 0; j < n; j++) {
         if (j < i) j = j + n;
         else x = x + 1;
      }

因此，对于这种算法，我的思考过程如下：

内循环执行n对jwhen的迭代i=0。但是，对于的每个值i=0,1..n-1，j只会执行一次迭代，因为if语句的求值为true并结束内部循环。

这是我的困惑来源：

由于外循环n无论如何都将执行迭代，并且由于内循环会n在i=0（第一次迭代）时执行迭代，因此big-Oh时间复杂度不是O（n²），而是O（n），如果循环是嵌套的，并且都n在第一次迭代中执行迭代？

Answer 1

您有一行这样的话if (j < i) j = j + n;，它实际上会跳出循环（when j < i），并且由于内部循环从0开始，因此每次（第一次除外）都会在第一次迭代时触发，从而使其以恒定的时间运行。

您在这里基本上只有一个循环。该代码可以重写为

int x = 0;
for (int i = 0; i < n; i++) {
    x = x + 1;
}

这清楚了为什么它是O（n）。