如果我有 k 个排序的单链表并按每个列表的最大元素(列表中的最后一个)对它们进行排序(合并排序),那么大 O(运行时间/时间复杂度)会是多少?假设列表 1 ~ k 有不同的大小:n_1 ~ n_k。我在想 O(k * log(MAX(n_1 ~ n_k))) 但不确定我是如何或为什么想到这种思路的。
最佳答案
假设你有 O(k) 个内存单元来存储每个列表的最大元素,合并排序列表本身的时间,即不合并它们的元素,将是 O(sum(Ni) + k*log k).
有第一项是因为您需要恰好导航到每个列表的末尾一次;之后,您可以使用最大值“标记”列表,并对标记列表执行合并排序。第二项来自使用合并排序对 k 个项目进行排序。原始列表已排序这一事实变得无关紧要,因为无论如何您都需要遍历整个列表。
如果列表是可修改的,即使没有额外的存储,时间复杂度也会保持不变,因为您可以反转列表,对它们进行排序,然后再次反转它们。反转列表需要 O(sum(Ni)),因此时间复杂度将保持不变。
关于algorithm - 按最大元素对 k 个排序列表进行排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/46446138/