问题描述
以下代码是O（n ^ 2）还是O（n）？
int i=0, j=0;
while (i < n) {
while (j < n) {
j++;
}
i++;
}
由于内部while循环仅从0到n运行一次，我认为它相当于具有两个单独的while循环，因此总运行时间将为O（2n）。
1楼
在这个特定的代码片段中是O（n）。 例如，对于i = 0，n = 10，内循环从j = 0到j = 9（10次）执行，而对于i = 1到9，内循环执行0次，（因为j（10）> n（10）将永远不会变为真），所以总时间=外部10倍+内部10倍= 20 = 2n因此时间复杂度为O（n）