我从我的算法教科书中有一个练习，我不太确定该解决方案。我需要解释为什么此解决方案：
function array_merge_sorted(array $foo, array $bar)
{
$baz = array_merge($foo, $bar);
$baz = array_unique($baz);
sort($baz);
return $baz;
}
合并两个数组并订购它们并不是最有效的，我需要提供一个最优化的解决方案，并证明可以做到更好的解决方案。
我的想法即将使用一个为o（n log n）的Mergesort算法，以合并并订购两个数组作为参数传递的数组。但是我如何证明这是有史以来最好的解决方案？
算法
您已经说过两个输入已经排序，您可以使用简单的 Zipper类似方法。
您有一个指向其开始的每个输入阵列的指针。然后，您比较两个元素，将较小的元素添加到结果中，并用较小的元素推进数组的指针。然后，您重复步骤，直到两个指针达到末端和所有元素添加到结果中。
您在Wikipedia＃合并算法中找到了此类算法的集合，而我当前提出的方法被列为合并两个列表。
这是一些 pseudocode ：
function Array<Element> mergeSorted(Array<Element> first, Array<Element> second) {
Array<Element> result = new Array<Element>(first.length + second.length);
int firstPointer = 0;
int secondPointer = 0;
while (firstPointer < first.length && secondPointer < first.length) {
Element elementOfFirst = first.get(firstPointer);
Element elementOfSecond = second.get(secondPointer);
if (elementOfFirst < elementOfSecond) {
result.add(elementOfFirst);
firstPointer = firstPointer + 1;
} else {
result.add(elementOfSecond);
secondPointer = secondPointer + 1;
}
}
}
证明
该算法显然在O(n)中起作用，其中n是结果列表的大小。或更确切地说是O(max(n, n')，n是第一个列表的大小，第二个列表的n'（或同一集的O(n + n')）。
这显然也是最佳，因为在某个时候需要一次traverse 所有元素一次，以构建结果并知道最终订购。对于此问题，这会产生Omega(n)的下限，因此该算法是最佳的。
更正式的证据假设一个更好的任意算法A可以解决问题没有来查看每个元素至少至少O(n)）。
我们称之为算法没有看的元素e。现在，我们可以构建一个输入I，以便e具有在其自身数组中满足顺序的值，但将被结果数组中的算法错误地放置。
我们能够为每种算法A做到这一点，并且由于A总是需要在所有可能的输入上正确工作，因此我们能够找到一个反例I，以使其失败。
因此，A 不能存在，而Omega(n)是下BOUNT BOND BOND BOND 对于该问题。
为什么给定算法更糟
您给定的算法首先合并两个阵列，这在O(n)中起作用，这很好。但是之后，它分类数组。
排序（更精确：基于比较的排序）具有较低的Omega(n log n)。这意味着每种这样的算法都不能比这更好。
因此，给定算法具有O(n log n)的总时间复杂性（由于排序部分）。比 O(n)，其他算法的复杂性和最佳解决方案都要差。
但是，要获得超级纠正，我们还需要争论 sort -Method是否会真正产生这种复杂性，因为它不会获得任意输入，但始终是的结果合并 -Method。因此，A 特定排序方法可能对此类特定输入特别有效，最终产生O(n)。
，但我怀疑这是您任务的重点。