合并k个排序数组的时间复杂度

Question

我有k个排序数组，每个长度为n，我想对它们进行排序，这样就有一个长度为n*k的排序数组。我知道我可以从合并排序中迭代应用合并函数。然而，我不明白为什么下面的代码是O（nk^2）而不是O（nk）。我在k数组上迭代一次，每个合并子例程相对于其输入具有线性时间。我错在哪里？如何更好地理解该算法的运行时间

def myMerge(left, right):
    l, r = 0, 0
    result = []
    for i in left+right:
        if left[l] <= right[r]:
            result.append(left[l])
            l += 1
            if l >= len(left):
                return result + right[r:]
        else:
            result.append(right[r])
            r += 1
            if r >= len(right):
                return result + left[l:]
    return result

#input
k = [[1,5,8],[2,7,9],[1,1,4]]

result = k[0]
for l in range(1,len(k)):
    result = myMerge(result,k[l])  

Answer 1

你的两个句子都是正确的：

• 在k数组上迭代一次
• 每个合并子例程相对于其输入具有线性时间

然而，答案是O（nk^2）。为什么?

因为上述输入的长度不是O（n）。在第一个循环之后，它已经是2*n了。第二次之后，已经是3*n了。等等因此，在上一次迭代中，数组长度为n*（k-1）和n，这意味着每个合并子例程都是O（nk），因此整个算法都是O（n*k^2）