<p>一般来说,生成随机输入并不是计算最坏情况下运行时间的好方法。例如,快速排序平均在O(n logn)中运行,但在最坏的情况下,它在O(n^2)中运行。然而,即使你生成了大量的随机样本,对于中等大的n,你永远不会接近最坏的情况。相反,请尝试手动构造最坏情况下的输入。在</p>
<p>在这种情况下,假设每个数组的长度为N,那么最坏的情况似乎发生在</p>
<pre><code>L1 = (N,2N,2N+1,...,3N-3,3N)
L2 = (N+1,N+2,...,2N-1,3N-1)
L3 = (1,2,...,N-1,3N-2)
</code></pre>
<p>要了解原因,请跟踪算法的执行情况。发生的第一件事是<code>L3</code>的前N-1个元素将被添加到<code>L</code>。循环的每个迭代都有3个比较:第一个<code>if</code>语句中有两个比较,第二个语句中有一个比较。注意,我们需要<code>L1[1]<L2[1]</code>,否则它将跳过第一个<code>if</code>中的第二个比较</p>
<p>接下来是元素<code>L[1]=N</code>,它只接受一个比较。在</p>
<p>在这之后是<code>L[2]</code>的前N-1个元素,每个元素都需要两个比较,一个到<code>L1</code>,一个到<code>L3</code>。在</p>
<p>接下来是来自<code>L1</code>的下一个N-2个元素,每个元素有一个比较。在</p>
<p>此时,每个列表中只剩下一个元素。<code>L3</code>首先选择3个比较,然后对<code>L2</code>进行一个比较,就这样。在</p>
<p>总数是</p>
^{pr2}$
<p>我认为这是最坏的情况,但你也许可以从中挤出一个。另外,我可能犯了一个错误,在这种情况下,这里的人可能会抓住它。下一步你应该做的是试着证明这是最坏情况下的运行时间。在</p>
<p>PS该算法对于合并三个列表不是最优的。从三个列表的前面选择最小的元素最多只需要2个比较,而不是3个。如果您发现<code>L2<L1</code>和{<cd14>},那么就没有必要比较<code>L2</code>和{<cd1>},因为您已经知道{<cd12>}更小。在</p>
<p>编辑:要证明这实际上是最坏的情况应该不难。假设没有一个列表为空,则每次迭代的比较次数为:</p>
<ul>
<li>3如果L3最小,L1<;L2</li>
<li>2如果L2最小</li>
<li>如果L1最小,则为1</li>
</ul>
<p>这就是N*6的上限,因为每个列表只能是最小的N次。因此,完成一个证明只需要检查在列表变空的末尾发生了什么。在</p>