资讯

历史

科技

环境与自然

成长

游戏

财经

文学与艺术

美食

健康

家居

文化

情感

汽车

三农

军事

旅行

运动

教育

生活

星座命理

算法设计优化：循环移位的三种实现方法

创作时间:

作者:

@小白创作中心

算法设计优化：循环移位的三种实现方法

引用

CSDN

https://blog.csdn.net/weixin_44399845/article/details/138045396

循环移位是算法设计中的一个经典问题，本文将介绍三种不同的实现方法：蛮力版、迭代版和倒置版。通过对比不同算法的时间复杂度和实现方式，帮助读者更好地理解循环移位的优化思路。

0. 循环移位

0.0 问题

仅用O(1)辅助空间，将数组A[0,n)中的元素向左循环移动k个单元。

1. 蛮力版 O(n*k)

算法思想：减而治之，实现移动1位，然后再循环k位。

1.1 代码示例

int shift ( int* A, int n, int s, int k ) { //从A[s]出发，以k为间隔循环左移，O(n / GCD(n, k))
   int bak = A[s]; //备份起始元素
   int i = s, j = ( s + k ) % n; //从该元素出发
   int mov = 0; //移动次数
   while ( s != j ) { //以k为间隔
      A[i] = A[j]; //依次左移k位
      i = j; j = ( j + k ) % n; mov++;
   }
   A[i] = bak; //将起始元素转入对应位置
   return mov + 1;
}

/*DSA*/int shift ( int* A, int n, int s, int t ); //从A[s]出发，以t为间隔循环左移，O(3n)
int shift0 ( int* A, int n, int k ) { //蛮力地将数组循环左移k位，O(nk)
   if ( k < 1 ) return 0; int mov = 0;
   while ( k-- ) { //反复以1为间隔循环左移，共迭代k次
      mov += shift ( A, n, 0, 1 );                                       /*DSA*/printf ( "== move *%3d\n", mov ); print ( A, n );
   }
   return mov;
}

1.2 时间复杂度

shift()算法每移动1位，需要向左移动n个元素，循环执行k次，故总体时间复杂度为O(n*k)。

2. 迭代版 O(n)

蛮力版复杂度高，因为k可能到O(n)量级。

改进思想：开始移动的数据的起始位和终止位都是已知的，如上图中的1号位为6，二号位为7等。

0号位被6填充
6号位被12填充
12号位被18填充
18号位被3填充

一轮下来，只需O(1)时间，但是不能保证所有的元素都能被解释到，因为可能有同余，同余位分布取决于n和k是否互素，如果不互素，则所有的元素都能被解释到。21和6有个最大公约数为3，所以0号归位，也只使得三分之一的元素归位，而且是均匀隔着三分之一，然后在以1为起始点开始。一般而言，如果最大公约数为g，经过g次迭代就可以了。

2.1 代码示例

int shift ( int* A, int n, int s, int k ) { //从A[s]出发，以k为间隔循环左移，O(n / GCD(n, k))
   int bak = A[s]; //备份起始元素
   int i = s, j = ( s + k ) % n; //从该元素出发
   int mov = 0; //移动次数
   while ( s != j ) { //以k为间隔
      A[i] = A[j]; //依次左移k位
      i = j; j = ( j + k ) % n; mov++;
   }
   A[i] = bak; //将起始元素转入对应位置
   return mov + 1;
}

/*DSA*/int shift ( int* A, int n, int s, int t ); //从A[s]出发，以t为间隔循环左移，O(3n)
int shift1 ( int* A, int n, int k ) { //通过GCD(n, k)轮迭代，将数组循环左移k位，O(n)
   if ( k < 1 ) return 0;
   int mov = 0, s = 0;
   while ( mov < n ) { //O(GCD(n, k)) = O(n*k/LCM(n, k))
      mov += shift ( A, n, s++, k );                                     /*DSA*/printf ( "== move *%3d\n", mov ); print ( A, n );
   }
   return mov;
}

2.1 时间复杂度

每个元素都是直奔主题的，不是亦步亦趋挪过去的，所以总体时间复杂度为O(n)。

3. 倒置版 O(3n)

算法思想：调用3次reverse，三次调用效果。以0、k、n为界，将序列分为L和R，经过3次reverse便可完成。

reverse思想：

无论何种实现，均由如下reverse()函数作为统一的启动入口

void reverse ( int*, int, int ); //重载的倒置算法原型
void reverse ( int* A, int n ) //数组倒置（算法的初始入口，调用的可能是reverse()的递归版或迭代版）
{ reverse ( A, 0, n - 1 ); } //由重载的入口启动递归或迭代算法

借助线性递归不难解决这一问题，为此只需注意到并利用如下事实：为得到整个数组的倒置，可以先对换其首、末元素，然后递归地倒置除这两个元素以外的部分。按照这一思路，可实现如下代码。其时间复杂度为O(n)。

void reverse ( int* A, int lo, int hi ) { //数组倒置（多递归基递归版）
   if ( lo < hi ) {
      swap ( A[lo], A[hi] ); //交换A[lo]和A[hi]
      reverse ( A, lo + 1, hi - 1 ); //递归倒置A(lo, hi)
   } //else隐含了两种递归基
} //O(hi - lo + 1)

时间复杂度分析

从中可以清楚地看出，每递归深入一层，入口参数lo和hi之间的差距必然缩小2，因此递归深度（亦即时间复杂度）为：(hi - lo) / 2 = n/2 = O(n)

3.1 代码示例

int shift2 ( int* A, int n, int k ) { //借助倒置算法，将数组循环左移k位，O(3n)
   k %= n; //确保k <= n
   reverse ( A, k ); //将区间A[0, k)倒置：O(3k/2)次操作
   /*DSA*/print ( A, n, 0, k );
   reverse ( A + k, n - k ); //将区间A[k, n)倒置：O(3(n - k)/2)次操作
   /*DSA*/print ( A, n, k, n );
   reverse ( A, n ); //倒置整个数组A[0, n)：O(3n/2)次操作
   /*DSA*/print ( A, n );
   return 3 * n; //返回累计操作次数，以便与其它算法比较：3/2 * (k + (n - k) + n) = 3n
}

这个算法很紧凑，没有涉及到上面版本数学上的东西要简单很多。