算法作业问题请教

[指着太阳说日]

You are given​

k lists, each one containing a sorted sequence of numbers.
Let n denote the total number of elements in all these lists.
Give an O(n log k)–time algorithm that merges these k lists into one sorted list.

Explain why the running time of your algorithm is O(n log k). ​

 

[dare2soar]

1. sort the first elements from k lists. O(k log k)
2. chose a smallest number for the sorted k tube. O(log k)
3. repeat n times step 2. O(n log k)

The running time should be: O(k log k)+O(n log k)

assume k<n

The running time: O(n log k).