Временная сложность объединения 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). После первого l oop это уже 2 * n. После второго уже 3 * n. И так далее. Таким образом, во время последней итерации длина вашего массива равна n * (k-1) и n, что означает, что каждая подпрограмма слияния равна O (nk), и, следовательно, весь алгоритм равен O (n * k ^ 2)