(2) 阅读 (1042)

块交换算法 编辑

词条创建者 匿名用户

块交换算法

编辑

计算机算法中,块交换算法交换一个数组中的两个元素区域。交换一个数组中大小相等的两个不重叠的区域很简单。然而,要将一个数组中的两个不重叠的区域原地互换,而这两个区域彼此相邻,但大小不等(这种互换相当于阵列旋转),则不简单。目前已知有三种算法可以完成这个任务。Bentley'sJuggling(也被称为Dolphin算法),Gries-Mills和Reversal。这三种算法都是线性时间O(n),(见时间复杂度)。

反转算法

编辑

反转算法是最简单的解释,使用旋转。旋转是数组元素的就地反转。这种方法将数组中的两个元素从外面换到一个范围内。旋转对偶数或奇数的数组元素都有效。反转算法使用三个就地旋转来完成一个就地块的互换。

块交换算法

旋转区域A

编辑

旋转区域B

旋转区域ABGries-Mills和Reversal算法比Bentley的Juggling表现得更好,因为它们对缓存友好的内存访问模式行为。Reversal算法的并行性很好,因为旋转可以被分割成子区域,这些子区域可以独立于其他区域进行旋转。


内容由匿名用户提供,本内容不代表vibaike.com立场,内容投诉举报请联系vibaike.com客服。如若转载,请注明出处:https://vibaike.com/163406/

发表评论

登录后才能评论

词条目录
  1. 块交换算法
  2. 反转算法
  3. 旋转区域A
  4. 旋转区域B

轻触这里

关闭目录

目录