这就是书中所说的问题:
Suppose you are given K sorted arrays each with n elements, and you want to combine them into a single array of kn elements. You use the following approach: first merge the first and second arrays, then merge the resulting array with the third array, then the resulting with the fourth, and so on until you merge in the kth and final input array. What is the running time taken by this successive merging algorithm, as a function of k and n, ignoring constant factors and lower-order terms.
我知道合并第一个和第二个数组时，最多进行 N 次比较，然后与第三个数组的结果进行最多 2N 次比较，然后与第四个数组合并最多有3N次比较等等。
这导致总共比较
N + 2N + 3N + 4N + ... + (k - 1)N
但是，我不太确定从这里到哪里去。我试过在线查看，但他们只给出了算术求和公式，但我不太了解它的数学原理，而且我不太确定如何包含 k，因为求和仅以 n 的形式给出。任何人都可以将我推向正确的方向或帮助我更好地理解这一点吗？
谢谢!
最佳答案
据我了解，您的问题是对 N + 2N + 3N + 4N + ... + (k - 1)N 求和。这等同于 N*(1+2+3+...+(k-1)) = N*(k-1)*(k)/2
顺便说一句，请注意合并两个大小为 N 的数组需要 2*N 比较(而不是 N)。所以正确的系列应该是:2N + 3N + ... + KN
S = 2N + 3N + ... + KN
S+N = 1N + 2N + 3N + ... + KN
S+N = N (1+2+3+...+K)
S+N = N*K*(K+1)/2
S = N*K*(K+1)/2 - N = O(N.K^2)
PS:我们知道从1到x的数之和是x*(x+1)/2
关于algorithm - 合并 K 个长度为 N 的排序数组，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/54777041/