Слияние K отсортированных массивов длины N

Question

Это проблема, описанная в книге:

Предположим, вам дано K отсортированных массивов, каждый из которых содержит n элементов, и вы хотите объединить их в один массив kn элементов.Вы используете следующий подход: сначала объедините первый и второй массивы, затем объедините результирующий массив с третьим массивом, затем результирующий с четвертым и т. Д., Пока вы не объедините k-й и последний входной массив.Сколько времени занимает этот алгоритм последовательного слияния как функция k и n , игнорируя постоянные коэффициенты и члены более низкого порядка.

Я знаю, что при слиянии первого и второго массивов у меня будет не более N сравнений, затем результат с третьим массивом, у меня будет не более 2N сравнений, затем слияние с четвертым массивом будет не более3N сравнения и т. Д.

В результате получается всего

N + 2N + 3N + 4N + ... + (k - 1) N

Однако я не совсем уверен, куда идти дальше.Я пытался смотреть онлайн, но они просто дают формулу арифметического суммирования, но я не совсем понимаю ее математику, и я не совсем уверен, как включить k, так как суммирование дается только через n.Кто-нибудь может подтолкнуть меня в правильном направлении или помочь мне лучше понять это?

Спасибо!

Answer 1

Значение tc должно быть O(N*k*(k-1)/2).

Также обратите внимание, что есть лучшее решение с решением O(k*n*lgk), использующее heap: leetcode

Answer 2

Как я понял, ваша проблема - подвести итог 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