if语句执行时间及指定求最小值代码中if语句T(n)的疑问

1. if语句的实际执行次数 #

先看你贴的这段Java代码：

public static int min(int[] v) { 
    int x = v[0]; 
    for (int i = 0; i < v.Length; i++) { 
        if (x >v[i]) x = v[i]; 
    } 
    return x; 
}

这里的for循环会完整执行n次（n是数组v的长度），每次循环里的if语句都会被执行一次——不管x > v[i]这个条件是否成立，只要循环走到这一行，条件判断的操作就完成了，所以if语句的总执行次数就是n次，也就是T(n) = n。

2. 关于时间复杂度的误区澄清 #

你的判断完全正确，这段代码的时间复杂度是O(n)，老师说的O(n²)应该是个误解，大概率是两种情况：

• 可能老师混淆了嵌套循环的场景——比如两层for循环嵌套里的if语句，那才会达到O(n²)的复杂度，但你这段代码只有一层线性循环，所有操作都是单次遍历数组的量级。
• 也有可能是老师口误，把线性复杂度错说成了平方复杂度。

我们来拆解一下时间复杂度的计算：

• 初始化x = v[0]是常数时间O(1)。
• for循环从i=0到i=n-1，共n次迭代：
  • 每次迭代的循环条件判断i < v.Length是O(1)。
  • if语句的条件判断是O(1)，哪怕进入分支执行x = v[i]，也是常数时间操作。
    所以整个函数的时间复杂度是O(n)，和if语句的执行次数完全匹配。

小提醒：别混淆“条件成立次数”和“语句执行次数” #

有时候有人会误以为只有if条件成立、进入分支时才算执行了if语句，但实际上只要代码执行到if这一行，完成了条件判断，就算执行了一次if语句。哪怕条件不成立，没有进入分支，这个判断操作已经完成了，所以这里的执行次数确实是n次。

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