python - 在 nlog(n/k) 中合并 n/k 排序列表 - python

Question

我有 round(n/k) 个排序的子列表，这意味着每个子列表的长度为 k(以及长度小于 k 的单个列表)。我需要使用经典的 O(m+n) 合并函数将它们合并到单个 n 长度的排序列表中，因此需要 O(n*log(n/k))。

我有两个实现，一个是递归的(这似乎是正确的，但除非我改变递归深度，否则不会工作，这是我不允许的，我不明白为什么实际上，当输入列表不超过 10 个子列表，每个子列表的长度为 k=3):

def merge_sorted_blocks(lst):
  i=0
  pairs_lst=[]
  n=len(lst)
  while i<n-1:
    pairs_lst.append(merge(lst[i],lst[i+1]))
    i+=2
  if n%2>0:
    pairs_lst.append(lst[n-1])
  if type(pairs_lst[0])!=list:
    return pairs_lst
  return merge_sorted_blocks(pairs_lst)

和一个与下一个子列表连续的输出列表:

def merge_sorted_blocks(lst):
  pairs_lst=[]
  for i in lst:
    pairs_lst=merge(pairs_lst,i)
  return pairs_lst

但我不认为它具有所需的复杂性，更像是 O(n*(k+2k+...))=O(n^2))。我发现这个线程暗示它确实如此，但我不明白如何: https://math.stackexchange.com/questions/881599/on-log-k-for-merging-of-k-lists-with-total-of-n-elements

关于这些解决方案，我是否遗漏了什么？

Answer 1

对于第二种算法，您的计算存在谬误。此外，您提到的线程与您的问题有一些差异。

你有 k 子列表，大小为 n/k。由于 merge 函数对于大小为 n1 和 n2 的两个集合的复杂度是 O(n1 + n2) ，两个子列表第一次合并的计算复杂度为O(2 * n/k)，当前子列表与第三个子列表的计算复杂度为O(3 * n/k)。因此，第二个算法的复杂度是 O(2*(n/k) + 3*(n/k) + ... + k*(n/k)) = O(nk).

对于第一次实现，遗漏了一些细节。例如，如果只有一组(例如最后一步)，循环将失败。

另外，第一种算法的复杂度分析不准确。如果要实现引用算法，算法为O(n/k * log(k))。