k个有序数组逐次合并算法的时间复杂度分析

让咱们一步步拆解这个问题，搞清楚逐次合并策略的运行时间：

首先明确基础前提：合并两个分别含m和p个元素的有序数组，时间复杂度是O(m + p)——毕竟每个元素都要被处理一次，忽略常数因子的话就是线性时间。

接下来看逐次合并的每一步开销：

• 第1次合并：合并前两个各含n个元素的数组，总元素数是2n，耗时O(2n)
• 第2次合并：把上一步的2n元素结果和第三个数组（n元素）合并，总元素数3n，耗时O(3n)
• 第3次合并：合并3n元素结果和第四个数组，耗时O(4n)
• ...
• 第k-1次合并：合并前k-1个数组合并后的(k-1)n元素结果，和第k个数组（n元素），耗时O(kn)

现在把所有步骤的时间加起来，总耗时就是：
O(2n + 3n + 4n + ... + kn)

我们可以把n提取出来，转化为：
O(n * (2 + 3 + ... + k))

接下来计算括号里的求和项：从2到k的整数和，等于从1到k的和减去1，也就是：
(k*(k+1)/2) - 1

因为我们忽略常数因子，所以这个求和项的主导项是k²/2，低次项和常数都可以直接忽略，简化为O(k²)。

所以最终总时间复杂度就是：
O(k²n)

举个直观的例子：如果k=5，n=10，总耗时就是20+30+40+50=140，而k²n=25*10=250，忽略常数后两者同属O(k²n)的复杂度级别，完全吻合。

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