5

好的,我知道 Mergesort 的最坏情况时间为 theta(NlogN),但它的开销很高,并且出现在进行合并的递归树的底部附近。有人建议我们在大小达到 K 时停止递归,并在此时切换到插入排序。我需要证明这个修改后的递归关系的运行时间是theta(NK + Nlog(N/k))?我对如何解决这个问题感到茫然..

4

1 回答 1

3

也许一个好的开始是查看这个问题的递归关系。我想对于典型的合并排序,它看起来像这样:

T(N) = 2 * T(N / 2) + N

即,您将问题划分为 2 个大小为一半的子问题,然后执行 N 个工作(合并)。我们有一个需要恒定时间的基本情况。

将其建模为一棵树,我们有:

T(N)   =   N   ->   T(N / 2)   
               ->   T(N / 2)

       =   N   ->   (N / 2)   ->   T(N / 4)
                              ->   T(N / 4)
               ->   (N / 2)   ->   T(N / 4)
                              ->   T(N / 4)

这给出了扩展

T(N) = N + 2N/2 + 4N/4 + ...
     = N + N + N ...

所以真的,我们只需要看看它有多深。我们知道i第 th 层对N / 2^i大小的子问题起作用。所以我们的叶节点 ( T(1)) 出现在以下L级别N / 2^L = 1

N / 2^L = 1
N = 2^L
log N = log(2^L)
log N = L

所以我们的运行时间是N log N.

现在我们介绍插入排序。我们的树看起来像这样

T(N) = ... -> I(K)
           -> I(K)
             ...x N/K

换句话说,我们将在某种程度上L必须解决N/Ksize 的插入排序问题K。插入排序的最坏情况运行时间为K^2. 所以在叶子上,我们总共有这么多工作:

(N / K) * I(K)
= (N / K) * K * K
= N * K

但是我们也有很多合并要做,N就像前面解释的那样,以树的每个级别为代价。回到我们之前的方法,让我们找到L(在我们达到大小子问题K并因此切换到插入之前的级别数):

N / 2^L = K
N / K = 2^L
L = log (N/K)

所以总的来说我们有

O(N) = N * K + N * log (N/K)

自从我用算法给你一个证明草图已经太久了,但这应该会让你的神经元兴奋起来。

于 2011-01-31T08:24:06.267 回答