含if语句的for循环时间复杂度计算及代码分析咨询

一、if语句在时间复杂度计算中的统计规则 #

计算时间复杂度时，要统计所有执行的操作步骤，包括if的条件判断——毕竟判断本身也是程序要做的工作。至于if内部的语句，只要它被执行，次数也要算，但最终复杂度看的是哪个操作的次数在n趋向无穷大时占主导地位：

• 如果if内部只是单次操作，且仅在少数情况触发，主导复杂度的就是条件判断的次数；
• 如果if内部嵌套了循环，那内部循环的执行次数才是决定复杂度的核心。

二、你的代码时间复杂度分析 #

先整理代码（补充了n的类型声明，修正语法问题）：

#include<iostream>
using namespace std;
int main()
{
    int i;
    int n=100;
    for(i = 0;i<n;i++)
    {
        if (i == n - 1)
            break;
    }
}

这段代码的执行逻辑：
从i=0开始，每次先判断i < n，成立则进入循环体；循环体内判断i == n-1，成立就执行break跳出循环，否则执行i++后回到循环条件判断。

当n=100时，i < n会被判断100次（i从0到99每个值都要判断一次），i == n-1同样会被判断100次，仅break只执行1次。当n无限增大时，这些判断操作的总次数和n呈线性正相关——n翻倍，操作次数也近似翻倍，因此这段代码的时间复杂度是O(n)，而非O(1)。

不要误以为break提前退出会让复杂度变成常数，实际上循环的条件判断和if的条件判断都执行了n次，整体操作次数随n线性增长，所以复杂度仍是O(n)。

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