Modified Merge Sort的大O分析（除以√n个数组，改为2）
Big O analysis of Modified Merge Sort (divide by √n arrays, instead 2)
我正在研究一种修改后的合并排序算法，使用类似的过程合并两个排序数组，但我想合并 √n 个大小为 √n 的排序数组。它将从一个大小为 n 的数组开始，然后递归地分成 √n 个子问题，如上所述。使用以下算法：
1.) Divide array of n elements into √n pieces
2.) Pass elements back into method for recursion
3.) Compare pieces from step 1
4.) Merge components together to form sorted array
我相当确定这是正确的算法，但我不确定如何找到大 O 运行 时间。非常感谢任何正确方向的指导！
关键部分是找出合并步骤的复杂度。假设使用与 2-way 情况类似的方法：
- 从所有
√n 个数组中找出最小元素是 O(√n)。
- 所有
n 个要合并的元素都需要这样做；当某些阵列耗尽时可能出现的边缘情况只会减少 O(√n) 的复杂性。
因此合并的复杂度是O(n√n)。展开循环：
其中 (*) 表示 T() 项的扩展。发现第 m 次扩展的模式：
T项的系数是 n 到 1/2 的幂和的幂，直到 m。T 项的参数是 1/2 的 m 次方。- 累计项
n 的 1 次方 + 1/2 的次方，直到 m。
将上述规则写成一个紧凑的系列：
(*)使用几何级数的标准公式。(**) 指出，对于 n 的幂总和，最高幂占主导地位 (1/2)。假设停止条件是一些小常数，可以是 n = 1:
请注意，随着 n 的增加，2^(1 - ...) 项消失。因此，第一项从上方以 O(n) 为界，后者被第二项遮盖。
The time complexity of √n-way merge-sort is therefore O(n^1.5), which is worse than the O(n log n) complexity of 2-way merge-sort.
我正在研究一种修改后的合并排序算法，使用类似的过程合并两个排序数组，但我想合并 √n 个大小为 √n 的排序数组。它将从一个大小为 n 的数组开始，然后递归地分成 √n 个子问题，如上所述。使用以下算法：
1.) Divide array of n elements into √n pieces
2.) Pass elements back into method for recursion
3.) Compare pieces from step 1
4.) Merge components together to form sorted array
我相当确定这是正确的算法，但我不确定如何找到大 O 运行 时间。非常感谢任何正确方向的指导！
关键部分是找出合并步骤的复杂度。假设使用与 2-way 情况类似的方法：
- 从所有
√n个数组中找出最小元素是O(√n)。 - 所有
n个要合并的元素都需要这样做；当某些阵列耗尽时可能出现的边缘情况只会减少O(√n)的复杂性。
因此合并的复杂度是O(n√n)。展开循环：
其中 (*) 表示 T() 项的扩展。发现第 m 次扩展的模式：
T项的系数是n到1/2的幂和的幂，直到m。T项的参数是1/2的m次方。- 累计项
n的 1 次方 +1/2的次方，直到m。
将上述规则写成一个紧凑的系列：
(*)使用几何级数的标准公式。(**)指出，对于n的幂总和，最高幂占主导地位 (1/2)。假设停止条件是一些小常数，可以是n = 1:
请注意，随着 n 的增加，2^(1 - ...) 项消失。因此，第一项从上方以 O(n) 为界，后者被第二项遮盖。
The time complexity of
√n-way merge-sort is thereforeO(n^1.5), which is worse than theO(n log n)complexity of 2-way merge-sort.