迭代合并k个有序数组为何时间复杂度是O(nk²)而非O(nk)？

嘿，我来帮你拆解这个问题里的时间复杂度误区～ 你提到“仅遍历k个数组一次，且每个合并子程序的时间复杂度相对于其输入呈线性”，这个说法本身没错，但你忽略了一个关键：每次合并的输入规模是在不断增长的，不是每次都只合并两个长度为n的数组。

一步步算清楚总操作量 #

我们来逐个分析你代码里的合并步骤（假设每个数组长度都是n，总共有k个数组）：

• 第1次合并：合并第1、2个数组，总长度是n + n = 2n，时间复杂度O(2n)
• 第2次合并：合并上一步的结果（长度2n）和第3个数组（长度n），总长度2n + n = 3n，时间复杂度O(3n)
• 第3次合并：合并长度3n的结果和第4个数组，总长度3n + n = 4n，时间复杂度O(4n)
• ...
• 第k-1次合并：合并长度(k-1)n的结果和第k个数组，总长度kn，时间复杂度O(kn)

现在把所有步骤的时间加起来：

总时间 = 2n + 3n + 4n + ... + kn
       = n × (2 + 3 + ... + k)

计算这个求和式：1到k的和是k(k+1)/2，所以2到k的和就是k(k+1)/2 - 1。当k很大时，这个值近似等于k²/2，所以总时间可以简化为n × k²/2，也就是O(nk²)。

你的误区在哪里？ #

你误以为“遍历k个数组一次”就对应O(nk)的时间，但实际上每次循环里的合并操作处理的元素数量越来越多。比如当k=100时，最后一次合并要处理99n + n = 100n个元素，前面的合并也都在处理比2n多的元素，总操作量远大于nk。

怎么更好理解这类算法的运行时间？ #

• 不要只看循环的次数，要累加每一步的实际操作量：如果循环里的工作量是变化的，不能直接用“循环次数 × 单次工作量”来计算，必须把每一步的工作量加起来分析。
• 对比最优的多路归并方式：如果用优先队列（最小堆）来做多路归并，每次取出最小元素的时间是O(logk)，总共nk个元素，总时间是O(nk logk)，比当前的O(nk²)高效得多（尤其是k较大时）。

举个具体的例子 #

用你给出的输入k = [[1,5,8],[2,7,9],[1,1,4]]（k=3，n=3）：

• 第一次合并处理6个元素，第二次合并处理9个元素，总操作数是6+9=15
• 而nk=9，15明显大于9，对应我们之前的公式n×(2+3)=3×5=15，和实际一致。

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