擅长:python、mysql、java
<p>线性时间意味着所用的时间由一些未定义的常数乘以(在本上下文中)要合并的两个列表中的项数限定。你的方法没有做到这一点-它需要O(n logn)时间。</p>
<p>当根据问题的大小指定一个算法需要多长时间时,我们忽略了诸如机器速度等细节,这基本上意味着我们忽略了所有常量项。我们用“渐近符号”来表示。这些基本描述了曲线的<em>形状</em>您将在问题大小x与时间y的关系图中绘制。逻辑是,如果问题足够大,一条糟糕的曲线(变得更陡峭的曲线)总是会导致执行时间变慢。对于一个非常小的问题(取决于常数,这可能取决于机器),它可能更快,但是对于小问题,执行时间通常不是一个大问题。</p>
<p>“big O”指定执行时间的上限。平均执行时间和下限都有相关的标注,但“大O”才是最受关注的。</p>
<ul>
<li>O(1)是恒定时间-问题大小无关紧要。</li>
<li>O(log n)是一条很浅的曲线-随着问题的扩大,时间会增加一些。</li>
<li>O(n)是线性时间-每增加一个单位意味着它需要大约恒定的额外时间。这张图大致是一条直线。</li>
<li>当问题变得更复杂时,O(n logn)曲线向上更陡,但不是很大。这是通用排序算法所能做的最好的事情。</li>
<li>当问题变得更复杂时,O(n平方)曲线向上陡峭得多。这对于较慢的排序算法(如冒泡排序)是典型的。</li>
</ul>
<p><strike>最糟糕的算法被归类为“np-hard”或“np-complete”,其中“np”表示“非多项式”-曲线比任何多项式都更快变陡。指数时间不好,但有些甚至更糟。这类事情仍在进行,但只针对非常小的问题。</strike></p>
<p><strong>编辑</strong>如注释所示,最后一段是错误的。我的算法理论确实有一些漏洞,显然是时候检查一下我认为我已经解决的问题了。同时,我也不太确定该怎么改那一段,所以请注意。</p>
<p>对于合并问题,请考虑您的两个输入列表已经排序。输出中的最小项必须是其中一个输入中的最小项。从二者中获取第一项并比较二者,然后将最小的项放入输出中。把最大的放回原处。你已经做了大量的工作,并且处理了一件事。重复,直到两个列表都用完。</p>
<p>一些细节。。。首先,将项目放回列表中只是为了再次将其拉出来显然是愚蠢的,但这使解释变得更容易。下一步-一个输入列表将在另一个之前耗尽,因此您需要处理这个问题(基本上只需清空另一个列表的其余部分并将其添加到输出中)。最后-你实际上不必从输入列表中删除条目-同样,这只是解释。你可以直接穿过它们。</p>