算法基本操作判定：最佳/平均/最坏场景规则与示例答疑

首先给出核心结论：最佳、平均、最坏三种时间复杂度分析场景下，基本操作的判定标准完全一致，不存在场景差异。
基本操作的核心定义是：算法执行过程中，单次执行成本为固定常数、耗时不随输入规模n变化的原子操作。你之前产生的认知偏差，本质是混淆了「基本操作」和「决定场景时间复杂度增长阶的高频主导操作」两个完全不同的概念。

针对示例代码的具体疑问解答 #

先给出分析所用的示例代码：

for i <- 0 to n-1
    if A[i] = Null
       return
    else
       if A[i] < 0
          # 省略固定常数步操作
       else if A[i] = 0
          for j <- 0 to n-1
             # 省略固定常数步操作
       else if A[i] > 0
          # 省略固定常数步操作

针对你的三个问题逐一明确答复：

• 关于最佳场景的判定：将A[i] = Null作为该场景下的专属基本操作是错误的。A[i] == Null本身属于分支比较类基本操作，但最佳场景的本质是输入使得所有基本操作的总执行次数取到最小值——也就是数组第一个元素就是Null，外层循环仅执行1次，仅完成1次数组空值判断就触发返回，总操作数为常数级，对应时间复杂度O(1)。这个结果和你选择哪类基本操作作为计数基准无关，只要是固定成本的基本操作，统计得到的时间增长阶完全一致。
• 关于最坏场景的判定：将A[i] = 0作为该场景下的专属基本操作是错误的。A[i] == 0同样是分支比较类基本操作，但它不是最坏场景下的主导操作。最坏场景的触发条件是数组遍历到最后一个元素才遇到值为0的项，此时会额外触发一轮长度为n的内层循环，总操作数和n²成正比，对应时间复杂度O(n²)。这里决定时间复杂度增长阶的是内层循环中重复执行的固定步操作，而非进入分支前的0值比较操作。
• 关于平均场景的判定：将4类数组元素比较操作作为平均场景的全部基本操作是错误的。所有满足固定单次执行成本的操作都属于基本操作范畴：数组下标取值、分支跳转、三个非空分支内的固定步操作、内层循环内的固定步操作，全部算基本操作。平均情况分析的核心是先给定所有合法输入的概率分布，再计算所有输入下基本操作总执行次数的加权期望，不需要单独把比较操作挑出来作为唯一计数对象。多数教材分析时习惯用比较操作计数，只是因为比较操作的执行次数和总基本操作执行次数呈固定线性比例，不会影响最终的增长阶结果，不代表只有比较操作才算基本操作。

关键澄清：做时间复杂度分析时，不需要为不同场景特意挑选不同的基本操作。不管统计哪类符合定义的基本操作的执行次数，最终得到的时间复杂度增长阶完全一致。很多教材对该部分表述模糊，是因为实际分析时不需要穷举所有基本操作，只需要选一个和总操作数呈固定常数倍比例的代表性操作计数即可，这种简化写法很容易造成“不同场景要换不同基本操作”的误解。

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