while循环时间复杂度计算：两个while循环应相加还是相乘

这段代码的整体时间复杂度为 O(n²)，其中n为初始时queueB中的元素总数（你的示例中n=4）。

核心疑问解答 #

两个while循环是同层级顺序执行的关系，同一轮外层for循环内两者的时间复杂度直接相加，不需要相乘；而外层for循环和内层的while循环是嵌套关系，两者的量级需要相乘。

具体推导过程 #

设初始queueB元素总数为n：

1. 外层for循环的执行轮次量级为O(n)：每轮循环会将2个元素从queueB+queueC转移到queueA，总共需要执行约n/2轮。
2. 单轮外层循环的操作量级为O(n)：
   • 第一个while循环：将当前queueB中除最后1个元素外的所有元素转移到queueC，执行次数为当前queueB长度-1
   • 第二个while循环：将当前queueC中除最后1个元素外的所有元素转移回queueB，执行次数为当前queueC长度-1
   • 两者加起来单轮操作次数和当前剩余元素规模成正比，平均量级为O(n)
3. 总时间复杂度为外层轮次 * 单轮操作量级 = O(n) * O(n) = O(n²)

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