如何合并两个列表并按"线性"时间对它们进行排序？

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表示法中的 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]

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"表示"非多项式" - 曲线比任何多项式更快.指数时间很糟糕,但有些甚至更糟.这些事情仍然存在,但仅限于非常小的问题.

编辑最后一段是错误的,如评论所示.我的算法理论确实有一些漏洞,显然是时候检查一下我认为我已经想到的东西了.与此同时,我不太确定如何纠正该段落,所以请加以警告.

对于合并问题,请考虑您的两个输入列表已经排序.输出中的最小项目必须是您输入中的最小项目.从两者中获取第一项并比较两者,并将最小值放在输出中.把最大的背部放在它的来源.你已经完成了一定数量的工作并处理了一个项目.重复,直到两个列表都用尽.

一些细节......首先,将项目放回列表只是为了将其重新拉出来显然是愚蠢的,但它使解释更容易.接下来 - 一个输入列表将在另一个输入列表之前耗尽,因此您需要处理它(基本上只清空其他列表的其余部分并将其添加到输出中).最后 - 你实际上不必从输入列表中删除项目 - 再次,这只是解释.你可以直接介绍它们.