对分成 x 个已排序部分的数组进行排序
Sorting an array which is split into x sorted parts
有人向我提出了两个 True/False 关于数组排序的问题。题目如下-
问题一
Given an array A with 3n keys that contains three equal parts
A[1,n], A[n+1,2n] and A[2n+1,3n], each with n keys. Each part is
sorted. Is possible to sort the keys of A into a
new array B in O(n) steps (worst case)?
问题B
Given an array A with 10n keys that are comparable using a binary function that returns which element
is bigger or if the elements are equal. The array is split into n equal parts, each
with 10 keys. Each part is sorted. Is it possible to sort the keys of
A into a new array B in O(n) steps (worst case)?
问题A的解决方案是我们可以使用MergeSort中的merge()函数对数组进行排序。
问题 B 的解决方案是不可能的，因为它违反了基于比较的排序算法的 Ω(nlog(n)) 下限
而且我看不出两道题的区别。。是不是因为B题要先应用函数？为什么它也禁止我们使用 merge() ？我看不出这两种情况不同的假设背后的逻辑，我觉得我遗漏了一些重要的东西。
根据问题 A：
很容易在O(n) 时间内对其进行排序。
算法工作如下 ->
1. You assign 3 pointers to the start of each sequence
2. You compare the element that pointers show to
3. Select one you needed (smallest or greatest) and push it to new array
4. Increase the pointer you have selected and continue from the first step till all 3 of the pointers reached end of the array
这就是归并排序的原理，这一点你是对的
问题B。
其实是一样的，不同的是在计算大O的时候，问题反过来了。在第一个问题中，我们将n作为数组中元素的数量，constant作为数组中元素的数量检查所以它转向 O(3n)=>O(n).
在第二种情况下，我们将 constant 作为元素的数量，数组的数量等于 n，因此计算将遵循 => O(n * 10)=>O(n).
最后我们得到了与 O(n) 完全相同的值，因为不管你有 3 个 n 元素的数组还是 n 个 3 个元素的数组，但前提是您不考虑比较。比较使总复杂度乘以 log(number of arrays)，因为这是比较所有内容的最少步骤数。
在第一种情况下 log(const) 可以忽略不计，在第二种情况下数组的数量是 n，所以我们得到 nlog(n) 的复杂性。
所以这就是这个任务的重点。
有人向我提出了两个 True/False 关于数组排序的问题。题目如下-
问题一
Given an array A with 3n keys that contains three equal parts A[1,n], A[n+1,2n] and A[2n+1,3n], each with n keys. Each part is sorted. Is possible to sort the keys of A into a new array B in O(n) steps (worst case)?
问题B
Given an array A with 10n keys that are comparable using a binary function that returns which element is bigger or if the elements are equal. The array is split into n equal parts, each with 10 keys. Each part is sorted. Is it possible to sort the keys of A into a new array B in O(n) steps (worst case)?
问题A的解决方案是我们可以使用MergeSort中的merge()函数对数组进行排序。
问题 B 的解决方案是不可能的，因为它违反了基于比较的排序算法的 Ω(nlog(n)) 下限
而且我看不出两道题的区别。。是不是因为B题要先应用函数？为什么它也禁止我们使用 merge() ？我看不出这两种情况不同的假设背后的逻辑，我觉得我遗漏了一些重要的东西。
根据问题 A：
很容易在O(n) 时间内对其进行排序。 算法工作如下 ->
1. You assign 3 pointers to the start of each sequence
2. You compare the element that pointers show to
3. Select one you needed (smallest or greatest) and push it to new array
4. Increase the pointer you have selected and continue from the first step till all 3 of the pointers reached end of the array
这就是归并排序的原理，这一点你是对的
问题B。
其实是一样的，不同的是在计算大O的时候，问题反过来了。在第一个问题中，我们将n作为数组中元素的数量，constant作为数组中元素的数量检查所以它转向 O(3n)=>O(n).
在第二种情况下，我们将 constant 作为元素的数量，数组的数量等于 n，因此计算将遵循 => O(n * 10)=>O(n).
最后我们得到了与 O(n) 完全相同的值，因为不管你有 3 个 n 元素的数组还是 n 个 3 个元素的数组，但前提是您不考虑比较。比较使总复杂度乘以 log(number of arrays)，因为这是比较所有内容的最少步骤数。
在第一种情况下 log(const) 可以忽略不计，在第二种情况下数组的数量是 n，所以我们得到 nlog(n) 的复杂性。
所以这就是这个任务的重点。