如何计算含嵌套if条件的while循环的时间复杂度

最终结论 #

你给出的双指针合并有序列表方法，时间复杂度为O(n+m)，其中n为列表a的长度，m为列表b的长度；存储结果的额外空间带来的空间复杂度同样为O(n+m)。

while循环的时间复杂度计算方法 #

你对while循环复杂度的疑惑核心是混淆了“条件触发执行”和“最坏执行次数统计”的逻辑：时间复杂度统计的是算法在最坏输入场景下，常数级基本操作的总执行次数量级，不需要循环“必然运行满固定次数”，只要找到循环执行过程中单调向终止条件推进的变量，计算该变量从初始状态到触发终止条件的最大步长，就能得到循环的最坏执行次数。

针对这段代码的三个while循环，我们可以逐段验证总执行次数：

1. 第一个双指针遍历的while循环
   循环终止条件是i >= a.size()或j >= b.size()。观察循环内的三个分支：无论进入哪个分支，每执行一次循环，i + j的总和至少增加1（仅i+1、仅j+1时总和+1，两数相等时i和j都+1，总和+2）。初始时i=0,j=0，i+j总和为0，循环终止时i+j最大为n+m（i走到n、j走到m的情况），因此这个循环的最多执行次数不会超过n+m次，且每次循环内的元素比较、ArrayList尾插操作都是均摊O(1)的常数级操作。
2. 后续两个补全剩余元素的while循环
   第一个循环结束时，i和j中至少有一个已经走到了对应列表的末尾，因此这两个循环永远只会触发最多一个，且执行的次数等于对应列表剩余未遍历的元素个数。
3. 总次数统计
   把三个循环的执行次数加总：第一个循环执行k次时，i+j的增量介于k和2k之间，剩余两个循环的总执行次数为(n-i)+(m-j)，总操作次数为k + (n-i)+(m-j) = n + m + (k - (i+j))。由于每轮循环i+j至少加1，因此k <= i+j，总操作次数永远不会超过n+m次，属于线性复杂度量级。

举两个极端场景验证：

• 当a所有元素都小于b时：第一个循环执行n次（i从0走到n，j始终为0），之后触发第三个循环遍历完b的m个元素，总操作数n+m。
• 当a和b元素完全一一相等时：第一个循环执行min(n,m)次（i和j同步递增），之后触发对应循环遍历完长列表剩余的|n-m|个元素，总操作数min(n,m)+|n-m|=n+m。

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