如何合并两个列表并在“线性”时间内对它们进行排序？

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

线性意味着Big O notation中的O（n），而代码使用的sort()最有可能是O(nlogn)。

问题是询问standard merge algorithm。一个简单的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]

Answer 2

Linear time表示程序的运行时与输入的长度成正比。在这种情况下，输入由两个列表组成。如果列表的长度是原来的两倍，那么程序将运行大约两倍的时间。技术上，我们说算法应该是O(n)，其中n是输入的大小（在本例中是两个输入列表的长度的总和）。

这似乎是家庭作业，所以我不会给你提供答案。尽管这不是家庭作业，但我认为你最好带上一支笔和一张纸，构建两个经过排序的小示例列表，并找出你如何手动合并这两个列表。一旦你明白了这一点，实现算法就轻而易举了。

（如果一切顺利，您将注意到您只需要在每个列表上以一个方向迭代一次。这意味着算法确实是线性的。祝你好运！）

Answer 3

线性时间意味着所用的时间由一些未定义的常数乘以（在本上下文中）要合并的两个列表中的项数限定。你的方法没有做到这一点-它需要O（n logn）时间。

当根据问题的大小指定一个算法需要多长时间时，我们忽略了诸如机器速度等细节，这基本上意味着我们忽略了所有常量项。我们用“渐近符号”来表示。这些基本描述了曲线的形状您将在问题大小x与时间y的关系图中绘制。逻辑是，如果问题足够大，一条糟糕的曲线（变得更陡峭的曲线）总是会导致执行时间变慢。对于一个非常小的问题（取决于常数，这可能取决于机器），它可能更快，但是对于小问题，执行时间通常不是一个大问题。

“big O”指定执行时间的上限。平均执行时间和下限都有相关的标注，但“大O”才是最受关注的。

• O（1）是恒定时间-问题大小无关紧要。
• O（log n）是一条很浅的曲线-随着问题的扩大，时间会增加一些。
• O（n）是线性时间-每增加一个单位意味着它需要大约恒定的额外时间。这张图大致是一条直线。
• 当问题变得更复杂时，O（n logn）曲线向上更陡，但不是很大。这是通用排序算法所能做的最好的事情。
• 当问题变得更复杂时，O（n平方）曲线向上陡峭得多。这对于较慢的排序算法（如冒泡排序）是典型的。

最糟糕的算法被归类为“np-hard”或“np-complete”，其中“np”表示“非多项式”-曲线比任何多项式都更快变陡。指数时间不好，但有些甚至更糟。这类事情仍在进行，但只针对非常小的问题。

编辑如注释所示，最后一段是错误的。我的算法理论确实有一些漏洞，显然是时候检查一下我认为我已经解决的问题了。同时，我也不太确定该怎么改那一段，所以请注意。

对于合并问题，请考虑您的两个输入列表已经排序。输出中的最小项必须是其中一个输入中的最小项。从二者中获取第一项并比较二者，然后将最小的项放入输出中。把最大的放回原处。你已经做了大量的工作，并且处理了一件事。重复，直到两个列表都用完。

一些细节。。。首先，将项目放回列表中只是为了再次将其拉出来显然是愚蠢的，但这使解释变得更容易。下一步-一个输入列表将在另一个之前耗尽，因此您需要处理这个问题（基本上只需清空另一个列表的其余部分并将其添加到输出中）。最后-你实际上不必从输入列表中删除条目-同样，这只是解释。你可以直接穿过它们。