选择阵列的最小长度为k的合并排序，其中使用插入排序的子数组排序比标准合并排序更优 [英] Choosing minimum length k of array for merge sort where use of insertion sort to sort the subarrays is more optimal than standard merge sort

问题描述

这是从算法导论通过Cormen的问题。但是，这不是一个家庭作业的问题，而不是自学。

This is a question from Introduction to Algorithms By Cormen. But this isn't a homework problem instead self-study.

有长度的数组 N 。考虑一个修改归并排序，其中 N / K 子列表的每个长度 K 的使用插入排序排序，然后合并使用合并机构，其中k是一个值来确定。

There is an array of length n. Consider a modification to merge sort in which n/k sublists each of length k are sorted using insertion sort and then merged using merging mechanism, where k is a value to be determined.

与的关系是N 和 K 不知道。数组的长度 N 。 K N / K的子列表办法 N *（N / K）等于阵列 N 元素。因此， K 仅仅是在该阵列与合并，排序使用的分裂停止，而不是插入排序是因为其较小的常数因子的限制。

The relationship between n and k isn't known. The length of array is n. k sublists of n/k means n * (n/k) equals n elements of the array. Hence k is simply a limit at which the splitting of array for use with merge-sort is stopped and instead insertion-sort is used because of its smaller constant factor.

我是能够做到的数学证明，改进后的算法在Θ（N * K + N * LG（N / K））最坏情况下的时间。现在这本书接着说

I was able to do the mathematical proof that the modified algorithm works in Θ(n*k + n*lg(n/k)) worst-case time. Now the book went on to say to

找到 K 最大价值的函数 N 要为其改进算法具有相同的运行时间作为标准归并排序，在Θ表示法的条款。我们应该如何选择K的做法呢？

find the largest value of k as a function of n for which this modified algorithm has the same running time as standard merge sort, in terms of Θ notation. How should we choose k in practice?

现在该让我思考了很多时间，但我不能拿出任何东西。我试图解决

Now this got me thinking for a lot of time but I couldn't come up with anything. I tried to solve

N * K + N * LG（N / K）= N * LG（N）的关系。我以为找到了2运行时间相等会给我的极限和更大的可使用简单的打了试验检查。

n*k + n*lg(n/k) = n*lg(n) for a relationship. I thought that finding an equality for the 2 running times would give me the limit and greater can be checked using simple hit-and-trial.

我解决它像这样

n k + n lg(n/k) = n  lg(n)

k + lg(n/k) = lg(n)

lg(2^k) + lg(n/k) = lg(n)

(2^k * n)/k = n

2^k = k

但它给了我 2 ^ k = k 不显示任何关系。是什么关系？我想我可能已经采取了错误的公式寻找的关系。

But it gave me 2 ^ k = k which doesn't show any relationship. What is the relationship? I think I might have taken the wrong equation for finding the relationship.

我可以实现的算法我猜想添加如果（length_Array＆LT; K）在语句 merge_sort 功能（的归并排序实现Github的链接）调用插入排序会不够好。但是，我该如何选择 K 在现实生活中？

I can implement the algorithm and I suppose adding an if (length_Array < k) statement in the merge_sort function here(Github link of merge sort implementation) for calling insertion sort would be good enough. But how do I choose k in real life?

推荐答案

那么，这是一个数学最小化问题，并解决它，我们需要一些基本的微积分。

Well, this is a mathematical minimization problem, and to solve it, we need some basic calculus.

我们需要找到 K 为其 D [N * K + N * LG（N / K）] / DK =价值= 0 。

我们还应该检查边缘的情况下，这是 K ==ñ和 K == 1

We should also check for the edge cases, which are k == n, and k == 1.

候选人为 K 的价值，这将使最小结果 N * K + N * LG（N / K）是最小的需要的范围内，因此是 K 。

The candidate for the value of k that will give the minimal result for n*k + n*lg(n/k) is the minimum in the required range, and is thus the optimal value of k.

附件，解决了derivitives公式：

Attachment, solving the derivitives equation:

d[n*k + n*lg(n/k)] / dk = d[n*k + nlg(n) - nlg(k)] / dk
= n + 0 - n*1/k = n - n/k 
=>
n - n/k = 0 => n = n/k => 1/k = 1 => k = 1

现在，我们有了人选：K = N，K = 1。对k = N，我们得到为O（n ^ 2），因此，我们得出结论：最佳 K 是 K == 1 。

Now, we have the candidates: k=n, k=1. For k=n we get O(n^2), thus we conclude optimal k is k == 1.

请注意，我们发现从大西塔的功能derivitives，而不是使用所需的常量精确的复杂功能。
这样做确切的复杂功能，所有的常数可能产生有一点不同的最终结果 - 但解决这个问题的方法是pretty的大致相同，只需要derivitives从不同的功能

Note that we found the derivitives on the function from the big Theta, and not on the exact complexity function that uses the needed constants.
Doing this on the exact complexity function, with all the constants might yield a bit different end result - but the way to solve it is pretty much the same, only take derivitives from a different function.

这篇关于选择阵列的最小长度为k的合并排序，其中使用插入排序的子数组排序比标准合并排序更优的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！