用单个while循环模拟嵌套for循环能否绕过O(n)时间复杂度限制？

1. 时间复杂度分析 #

你的这段代码和双层for循环完全等价，时间复杂度是O(n²)，不是O(n)。

看代码逻辑：i从0到n-1，每个i对应的j都会从0遍历到n-1，循环体总共会执行n*n次。时间复杂度只看实际执行的操作次数，和循环的写法无关——不管用双层for还是单个while，只要遍历的是所有i和j的组合，运算量就是n的平方量级。比如n=3时循环体执行9次，n=4时执行16次，明显符合O(n²)的特征。

2. 编程竞赛中能否绕过O(n)时间限制？ #

完全不能。

编程竞赛的时间限制是根据实际运算量判定的，不是看循环的层级数量。如果题目要求O(n)的时间复杂度，意味着最多允许执行约1e6~1e7次操作（具体看评测机性能）。而你的代码是O(n²)，当n达到1e4时，操作次数就会突破1e8，远远超过O(n)的上限，必然会超时——不管用while还是for来写，运算量的本质没变，不可能绕过限制。

附修正格式后的代码 #

#include<bits/stdc++.h>
using namespace std;

int main(){
    int i=0, j=0, n;
    cin>>n;

    while(i<n && j<n){
        cout<<i<<" "<<j<<endl;

        if(j==n-1){
            ++i;
            j=0;
        }
        else{
            j++;
        }

    }

    return 0;
}

内容的提问来源于stack exchange，提问作者Nripesh