3路和2路合并排序不失一般性?
3-way and 2-way merge sort without loss of generality?
所以,我正在研究 3 向归并排序,我想知道它是否不失一般性。
假设我们有数组 A' 的 3 个元素的幂和 A 的任意常数的幂。
这是我的问题。
为什么假设 n(元素的数量)是三的幂而不失一般性?
为什么任何形式的假设 n 是常数的幂也不失一般性?
因为你总是可以扩大数组 A 以适应你想要的大小,只是为了让算法起作用。
实际实现可能会也可能不会使用该假设,但原则上采用该假设不会阻止您将该算法应用于任何大小的任何数组 A。关于size的假设是有的,因为它简化了算法,方便分析时间和复杂度。
所以,我正在研究 3 向归并排序,我想知道它是否不失一般性。
假设我们有数组 A' 的 3 个元素的幂和 A 的任意常数的幂。
这是我的问题。
为什么假设 n(元素的数量)是三的幂而不失一般性?
为什么任何形式的假设 n 是常数的幂也不失一般性?
因为你总是可以扩大数组 A 以适应你想要的大小,只是为了让算法起作用。
实际实现可能会也可能不会使用该假设,但原则上采用该假设不会阻止您将该算法应用于任何大小的任何数组 A。关于size的假设是有的,因为它简化了算法,方便分析时间和复杂度。