请求验证两段算法的Big-O时间复杂度分析结果

咱们来逐一检查你的两个时间复杂度分析，先从第一段代码开始：

第一段代码分析 #

你的代码片段：

for (i = 1; i <= n; i++) { 
    for (j = 2*i; j <= n; j++) { 
        puts("hello"); 
    } 
}

你的分析结论O(N²)是完全正确的，不过计算过程可以更简洁——Big-O标记会忽略所有常数项和低阶项，不用纠结初始化、循环判断这些细节的计数。

关于你对j=2*i的边界疑问：内层循环的执行次数确实会随i增大而减少，咱们可以直接计算总执行次数的量级：
当i=1时，j从2到n，执行n-1次；
i=2时，j从4到n，执行n-3次；
...
直到i超过n/2时，内层循环不再执行。
总次数是一个等差数列求和，最终结果的量级是n²/4，忽略常数系数后就是O(n²)，所以你的结论没问题。

第二段代码分析 #

你的代码片段：

for (i = 1; i <= n; i++) { 
    for (j = 1; j <= n; j++) { 
        for (k = 1; k <= 200; k++) { 
            printf("%d %d\n", i, j); 
        } 
    } 
}

你的困惑非常典型，不过你的结论O(N²)是正确的。

第三层循环的执行次数是固定的200次，这是一个常数——不管n多大，它都不会随n变化。三重嵌套的时间复杂度是否为O(n³)，核心看每一层是否和n相关：这里前两层是O(n)的循环，第三层是O(1)的常数循环，所以总时间复杂度是O(n * n * 1) = O(n²)。常数项200在Big-O标记里会被直接忽略，不用把它揉进复杂的表达式里，抓住核心量级即可。

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