如何在“线性”时间内合并并排序两个列表？

Question

我有这个代码，它能正常工作：

# E. Given two lists sorted in increasing order, create and return a merged
# list of all the elements in sorted order. You may modify the passed in lists.
# Ideally, the solution should work in "linear" time, making a single
# pass of both lists.
def linear_merge(list1, list2):
  finalList = []
  for item in list1:
    finalList.append(item)
  for item in list2:
    finalList.append(item)
  finalList.sort()
  return finalList
  # +++your code here+++
  return

但是，我真的很想把这些东西学好。:) “线性”时间是什么意思呢？

Answer 1

线性时间指的是程序运行的时间和输入的长度成正比。在这个例子中，输入包含两个列表。如果这两个列表的长度变成原来的两倍，那么程序的运行时间大约也会变成原来的两倍。专业说法是，我们说这个算法的复杂度是O(n)，这里的n是输入的大小（在这个例子中，就是两个列表的总长度）。

这看起来像是作业，所以我不会给你答案。虽然这不是作业，但我认为你最好拿一支笔和一张纸，自己构造两个小一点的已排序的示例列表，然后想想你是怎么把这两个列表合并在一起的，手动操作一下。一旦你搞明白了这个过程，写出这个算法就简单多了。

（如果一切顺利，你会发现你只需要一次遍历每个列表，朝一个方向走。这意味着这个算法确实是线性的。祝你好运！）

Answer 2

线性时间的意思是，处理的时间受某个不确定的常数和你想合并的两个列表中的项目数量的乘积限制。你的方法没有达到这个标准，它的时间复杂度是O(n log n)。

在描述一个算法的运行时间时，我们通常不考虑机器的速度等细节，这基本上就是忽略所有常数项。我们用“渐进符号”来表示这些。它们主要描述的是你在图表中绘制的问题规模（x轴）与所需时间（y轴）之间的关系曲线的“形状”。逻辑是，如果曲线很陡（也就是增长得很快），那么在问题规模足够大的时候，执行时间就会变得更慢。虽然在非常小的问题上可能会更快（这取决于常数，可能还和机器有关），但对于小问题来说，执行时间通常不是个大问题。

“大O”表示执行时间的上限。还有一些相关的符号用于表示平均执行时间和下限，但“大O”是最受关注的。

• O(1) 是常数时间 - 问题规模不影响时间。
• O(log n) 是一个比较平缓的曲线 - 随着问题规模增大，时间只会稍微增加。
• O(n) 是线性时间 - 每增加一个单位，所需的时间大致是固定的。图表大致呈直线。
• O(n log n) 随着问题复杂度的增加，曲线会更陡，但不会太多。这是通用排序算法能做到的最好效果。
• O(n²) 随着问题复杂度的增加，曲线会陡得多。这通常是像冒泡排序这样的慢排序算法的表现。

最糟糕的算法被称为“np-hard”或“np-complete”，其中“np”表示“非多项式” - 这意味着曲线比任何多项式增长得更快。指数时间是糟糕的，但有些甚至更糟。这类算法仍然会被使用，但仅限于非常小的问题。

编辑：最后一段是错误的，评论中也提到了这一点。我在算法理论上确实有一些漏洞，显然是时候检查一下我“认为”自己已经搞明白的东西了。与此同时，我不太确定如何纠正那段话，所以请注意。

对于你的合并问题，考虑到你的两个输入列表已经是排序好的。输出中最小的项目必须是你输入中最小的项目之一。先从两个列表中取出第一个项目进行比较，把较小的放入输出中。把较大的项目放回原处。这样你就完成了一定量的工作，并处理了一个项目。重复这个过程，直到两个列表都处理完。

一些细节……首先，把项目放回列表再取出来显然是没必要的，但这样解释起来更简单。接下来，一个输入列表会比另一个先处理完，所以你需要处理这个情况（基本上就是把另一个列表剩下的内容全部加入输出）。最后，实际上你并不需要从输入列表中移除项目 - 这只是为了方便解释。你可以直接遍历它们。

Answer 3

线性意味着在大O符号中是O(n)，而你的代码使用了一个sort()函数，这个函数很可能是O(nlogn)。

这个问题是在询问标准的合并算法。下面是一个简单的Python实现：

def merge(l, m):
    result = []
    i = j = 0
    total = len(l) + len(m)
    while len(result) != total:
        if len(l) == i:
            result += m[j:]
            break
        elif len(m) == j:
            result += l[i:]
            break
        elif l[i] < m[j]:
            result.append(l[i])
            i += 1
        else:
            result.append(m[j])
            j += 1
    return result

>>> merge([1,2,6,7], [1,3,5,9])
[1, 1, 2, 3, 5, 6, 7, 9]