algorithm - 3路和2路合并排序不失一般性？

Question

所以，我正在研究 3 向归并排序，我想知道它是否不失一般性。

让我们假设我们有数组 A' 的 3 个元素的幂和 A 的任何常数的幂。

这是我的问题。

1. 为什么假设 n(元素数)是 3 的幂而不失一般性？

2. 为什么 n 是常数的幂这种形式的任何假设也不失一般性？

Answer 1

因为您总是可以扩大数组 A 以适应您想要的大小，只是为了使算法起作用。

实际实现可能会也可能不会使用该假设，但原则上采用该假设不会阻止您将该算法应用于任何大小的任何数组 A。之所以有大小假设，是因为它简化了算法，便于分析时间和复杂度。