块交换算法
编辑在计算机算法中,块交换算法交换一个数组中的两个元素区域。交换一个数组中大小相等的两个不重叠的区域很简单。然而,要将一个数组中的两个不重叠的区域原地互换,而这两个区域彼此相邻,但大小不等(这种互换相当于阵列旋转),则不简单。目前已知有三种算法可以完成这个任务。Bentley'sJuggling(也被称为Dolphin算法),Gries-Mills和Reversal。这三种算法都是线性时间O(n),(见时间复杂度)。
反转算法
编辑反转算法是最简单的解释,使用旋转。旋转是数组元素的就地反转。这种方法将数组中的两个元素从外面换到一个范围内。旋转对偶数或奇数的数组元素都有效。反转算法使用三个就地旋转来完成一个就地块的互换。
旋转区域A
编辑旋转区域B
旋转区域ABGries-Mills和Reversal算法比Bentley的Juggling表现得更好,因为它们对缓存友好的内存访问模式行为。Reversal算法的并行性很好,因为旋转可以被分割成子区域,这些子区域可以独立于其他区域进行旋转。
内容由匿名用户提供,本内容不代表vibaike.com立场,内容投诉举报请联系vibaike.com客服。如若转载,请注明出处:https://vibaike.com/163406/