循环右移----由简单到卓越 - 夜风依旧的博客

作者在 2008-06-05 17:14:19 发布以下内容

/*************************************************************************************\

命题：数组array，长度为n，要求向右循环移动k位(0<k < n)，时间复杂度和空间复杂度尽可能小。

\*************************************************************************************/

一、第一反应

对于初次遇到此命题的人，一般都会这么做：先设置一个零时变量，将数组最后一个存入变量，然后将数组中前n-1个，从最后一个开始，依次存入后面一个位置，这样做的效果就把前n-1个整体向右平移一个单位，再把零时变量的值存入数组头，如此数组完成了向右循环移动1位的工作，再外加一个循环控制，循环右移k次，于是便完成了。代码如下：

template<typename T>

void cycle_move(T* array,int n,int k)

{

for(int i = 0;i < k;i++) //k次循环右移

{

T temp = array[n-1]; //设置零时变量

for(int j = n - 1;j > 0 ;j--)

array[j] = array[j - 1];

array[0] = temp;

}

这是最直观的解法，算法外循环k次，内循环n-1次，k (k=1,2…n-1)是个随机值,等概率分布，循环次数的数学期望=[1*1/(n-1)+2*/(n-1)+…+(n-1)*1/(n-1)]*(n-1)=n(n-1)/2,所以时间复杂度为O(n2)，空间复杂度为O(1)。时间复杂度难以让人接受。

二、换位思考

前一种方法目的是将后面的k个数据一个个的移到前面，可以换过来想想:将前面的一次性放到所要放的地方。

如：0 1 2 3 4 5 6 7右移3位

将0移到第三位，1移到第1+3位……如此原来的数需要保存，于是可以很容易想到：将0和3交换，但3也需要移到3+3位，于是可以交换此时的第0位和第6位，于是交换后第0位是6，而此时的6+3位则需要取8的模（6+3）%8=1，于是跟第1位交换……

于是大概的雏形便出现了：每次用第一位跟第（i+k）% n位的数据交换，终止条件是模为0。

伪代码如下：

/*******************************************\

1. i = 0

2. i = (i + k)% n

3. if(i == 0) 退出循环

4. swap(array[0],array[i]),转到第步

\********************************************/

貌似很简单，但是问题便出来了，（i+k）% n能访问到数组中所有的位置吗？如果能，那么每个位置是否只被访问了一次？下面将继续探讨。

三、深入探讨

首先举几个例子。

例一：0 1 2 3 4 5 6 7右移3位（n=8,k=3）

第1次	3	1	2	4	5	6	7
第2次	6	1	2	4	5	3	7
第3次	1	6	2	4	5	3	7
第4次	4	6	2	1	5	3	7
第5次	7	6	2	1	5	3	4
第6次	2	6	7	1	5	3	4
第7次	5	6	7	1	2	3	4

循环了7次，i访问了所有点，且仅仅访问了一次。

例二：0 1 2 3 4 5 6 7 8右移3位（n=9,k=3）

第1次	3	1	2	0	4	5	6	7	8
第2次	6	1	2	0	4	5	3	7	8

第3次时i = (i+k)%n = 0;于是出故障了。

例三：0 1 2 3 4 5 6 7 9右移6位（n=9,k=6）

第1次	6	1	2	3	4	5	0	7	8
第2次	3	1	2	6	4	5	3	7	8

第3次时i = (i+k)%n = 0;于是也出故障了。

再细想一下也很容易发现，当n是k的整数倍时，循环（n/k – 1）次一定会回到第0位，这是很显然的。而且条件可以更宽些，当n跟k不是互质时，循环[ n/(n,k) – 1 ]次也会回到第0位( (n,k)表示n和k的最大公约数)。

于是我们先看看(n,k) = 1时(即互质)。

1. (n,k) = 1时的情况

/************************************************\

已知(n,k) = 1

i = 0;

i = (i + k)%n;

当i == 0 时退出

求证：i可以访问数组中的每一个元素，且仅访问一次

\************************************************/

这个证明很简单：

<1>我们可以先取j = 0; j = j + k;跟i同时循环，则I = (I + k)%n 跟 j%n 是等价的。当I = (I + k)%n = 0时，则有j%n = 0，而j = j + k = pk (j初值为0，p为一正整数)，于是pk%n = 0，即 pk是n的倍数，而k跟n是互质的，所以p是n的倍数，又因为只要pk%n = 0,则退出，所以p是n最小的倍数，所以必有p = n。所以i共访问了n个元素。

<2>因为I = j%n，设不同时刻的i1,i2，i1 – i2 = (j1 – j2)%n = (p1*k – p2*k)%n = (p1 – p2)*k%n，若i1 = i2，则p1 – p2一定是n的倍数，显然不同时刻p1 != p2(因为j是递增的)，所以任意时刻i1 != i2。即i对n产生的模互不相等。

<3>综合1、2，得i对n的所有余数一一映射，则必然可以得到i可以访问数组中的每一个元素，且仅访问一次。

于是对于(k,n) = 1的情况可以写出代码：

template<typename T>

void cycle_move(T* array,int n,int k)

{

int i = 0;

while((i = (i + k) % n) != 0)

swap(array[0],array[i]);

}

2.考虑(k,n) != 1的情况

这种情况，有一个及其简单的思路----分段。

设(k,n) = m，则可以把n个数看成每段长度为m的n/m段数据的集合。例如:

0 1 2 3 4 5 6 7 8右移6位（n=9,k=6,m=3）

可以看成：

{0 1 2} {3 4 5} {6 7 8}三段，

此时向右移动6位即将这三段向右移动2 段(2 = k / m)，鉴于前面的程序，则可以将每段中同一个位置的元素看成可以移动的集合，如{0 3 6}，此时的n’跟k’必然是互质的，于是可以内嵌上面的一段程序。于是可以这样组织代码：

int greatest_common(int m,int n) //求出最大公约数

{

int r;

while(r = m % n) { m = n; n = r; }

return n;

}

template<typename T>

void cycle_move(T* array,int n,int k)

{

int r = greatest_common(n,k);

for(int i = 0;i < r;i++)

{

int j = i;

while((j = (j + k) % n) != i)

swap(array[0],array[j]);

}

四、多一点思考

前面所做的一切都是为了这段代码，而这段代码却如此简练。

复杂度分析：

求最大公约数时间复杂度为O(logn), cycle_move循环次数为n，而logn < n

所以该算法时间复杂度为O(n)。空间复杂度为O(1)，产生在交换中。

事情到这里似乎已经很完美了，但何不多想一点？

这个程序最不好的地方在哪里呢？

很显然，最不好的地方在交换！每循环一次就得交换一次，二交换的实现类似于：

template<typename T>

void swap(T& left,T& right)

{

T temp = left;

left = right;

right = temp;

}

需要频繁地使用数组下表和这三个赋值语句，这就是我们需要改善的。

那么如何避免交换呢？

下面仍然先从(k,n) = 1说起。

前一种方法中，所有数据通过第0位作中转，以存储到目标位置，这就是交换产生的原因。如果另设一个中转的变量temp，源数据保存在temp中，每次需要将temp中的数据存到目标位，但此时目标位的数据就需要保存下来，如果保存下来了，则以此类推，得到最后一个被访问的（也就是第0位）需要被保存。这样一来就豁然开朗了：只要先保存第0位，然后按照跟前面 i 访问次序相反的次序访问，就可以不被覆盖。于是又得到下面的代码：

template<typename T>

void cycle_move(T* array,int n,int k)

{

T temp = array[0];

int i = 0,prei;

while((prei = (n + i - k) % n) != 0)

{

array[i] = array[prei];

i = prei;

}

array[i] = temp;

}

于是对于(k,n)!=1的情况可以这样组织代码：

template<typename T>

算法 | 阅读 3869 次

文章评论，共7条

夜风依旧(作者)

2008-06-05 17:37

部分小于号或尖括号被转义了

赞回复

tengzhao201

2010-04-28 10:30

//最高效的循环右移算法！！ 
//这个是递归的写法 
//author:tengzhao201 QQ:715572192 
//time:2010-4-24 
//时间复杂度为O(n)，空间复杂度O(1)，交换点在中间时比逆序法快一倍！！！ 
void TZshift1(int a[],int N,int K) 
{ 
        K=K%N; 
 
        if(0==K)return; 
 
        int temp,qq,pp=0; 
        pp=0;qq=K; 
        for(int i=0;i<N-K;i++,pp++,qq++) 
        { 
                //swap(a[i%K],a[i+K]);问题的关键在于找到原来的第i个元素现在在哪里，通过观察可以发现在a[i%K]的位置，下面的代码实现了a[i%K]和a[i+K]的互换 
                if(K==pp)pp=0; 
                temp=a[pp]; 
                a[pp]=a[qq]; 
                a[qq]=temp; 
        } 
 
        TZshift1(a,K,K-pp); 
} 
 
//最高效的循环右移算法！！ 
//非递归的写法 
//author:tengzhao201 QQ:715572192 
//time:2010-4-24 
//时间复杂度为O(n)，空间复杂度O(1)，交换点在中间时比逆序法快一倍！！！ 
void TZshift0(int a[],int N,int K) 
{ 
        K=K%N; 
        if(0==K) 
                return; 
 
        //int count=0; 
        int temp,qq,pp=0; 
 
        while(K>0) 
        { 
                pp=0;qq=K; 
                for(int i=0;i<N-K;i++,pp++,qq++) 
                { 
                        //swap(a[i%K],a[i+K]);问题的关键在于找到原来的第i个元素现在在哪里，通过观察可以发现在a[i%K]的位置，下面的代码实现了a[i%K]和a[i+K]的互换 
 
                        if(K==pp)pp=0; 
                        temp=a[pp]; 
                        a[pp]=a[qq]; 
                        a[qq]=temp; 
                        //count+=2; 
                } 
                N=K; 
                if(0==pp) 
                        return; 
                K-=pp; 
                //TZshift(a,K,K-pp); 
        } 
        //cout<<"In tatal,has used "<<count<<" steps."<<endl; 
}

赞回复

tengzhao201

2010-04-28 13:20

经过测试，比楼主的求最大公约数的算法快一倍！

赞回复

夜风依旧(作者)

2010-04-28 23:29

<div class="quote">tengzhao201: 经过测试，比楼主的求最大公约数的算法快一倍！</div>其实我慢在太多的取模运算，我优化了一下，终于比你快了！！！

赞回复

夜风依旧(作者)

2010-04-28 23:30

<div class="quote">tengzhao201: 经过测试，比楼主的求最大公约数的算法快一倍！</div>#include <algorithm> 
#include <iostream> 
 
using namespace std; 
 
//最高效的循环右移算法！！ 
//这个是递归的写法 
//author:tengzhao201 QQ:715572192 
//time:2010-4-24 
//时间复杂度为O(n)，空间复杂度O(1)，交换点在中间时比逆序法快一倍！！！ 
void TZshift1(int a[],int N,int K) 
{ 
    K=K%N; 
 
    if(0==K)return; 
 
    int temp,qq,pp=0; 
    pp=0;qq=K; 
    for(int i=0;i<N-K;i++,pp++,qq++) 
    { 
        //swap(a[i%K],a[i+K]);问题的关键在于找到原来的第i个元素现在在哪里，通过观察可以发现在a[i%K]的位置，下面的代码实现了 a[i%K]和a[i+K]的互换 
        if(K==pp)pp=0; 
        temp=a[pp]; 
        a[pp]=a[qq]; 
        a[qq]=temp; 
    } 
 
    TZshift1(a,K,K-pp); 
} 
 
//最高效的循环右移算法！！ 
//非递归的写法 
//author:tengzhao201 QQ:715572192 
//time:2010-4-24 
//时间复杂度为O(n)，空间复杂度O(1)，交换点在中间时比逆序法快一倍！！！ 
void TZshift0(int a[],int N,int K) 
{ 
    K=K%N; 
    if(0==K) 
        return; 
 
    //int count=0; 
    int temp,qq,pp=0; 
 
    while(K>0) 
    { 
        pp=0;qq=K; 
        for(int i=0;i<N-K;i++,pp++,qq++) 
        { 
            //swap(a[i%K],a[i+K]);问题的关键在于找到原来的第i个元素现在在哪里，通过观察可以发现在a[i%K]的位置，下面的代码实现了 a[i%K]和a[i+K]的互换 
 
            if(K==pp) 
                pp=0; 
            temp=a[pp]; 
            a[pp]=a[qq]; 
            a[qq]=temp; 
            //count+=2; 
        } 
        N=K; 
        if(0==pp) 
            return; 
        K-=pp; 
        //TZshift(a,K,K-pp); 
    } 
    //cout<<"In tatal,has used "<<count<<" steps."<<endl; 
} 
 
int greatest_common(int  m,int  n)      //求出最大公约数 
{ 
    while(n) { 
        m %= n; 
        if(m == 0) { 
            return n; 
        } 
        n %= m; 
    } 
    return m; 
} 
 
template<typename T> 
void cycle_move(T* array,int n,int k) 
{ 
    k %= n; 
    int r = greatest_common(k,n); 
    for(int i = 0;i < r;i++) 
    { 
        int t = i + k; 
        int prej = i; 
        int j = t; 
        T tmp = array[j]; 
        do { 
            array[j] = array[prej]; 
            j = prej; 
            prej -= k; 
            if(prej < 0) { 
                prej += n; 
            } 
        }while(prej != t); 
        array[j] = tmp; 
    } 
} 
 
#include "MsClock.h" 
 
int main() { 
    const int N = 100; 
    const int K = 55; 
    const int R = 100000; 
    int a[N]; 
 
    for(int i = 0;i < N;i++) { 
        a = i; 
    } 
 
     MsClock clk; 
     for(int i = 0;i < R;i++) { 
         TZshift0(a,N,K); 
         TZshift0(a,N,N-K); 
     } 
     cout<<clk.Now()<<endl; 
     copy(a,a+N,ostream_iterator<int>(cout," ")); 
     cout<<endl; 
 
     clk.Restart(); 
     for(int i = 0;i < R;i++) { 
        cycle_move(a,N,K); 
         cycle_move(a,N,N-K); 
     } 
     cout<<clk.Now()<<endl; 
     copy(a,a+N,ostream_iterator<int>(cout," ")); 
     cout<<endl; 
 
    return 0; 
}

赞回复

夜风依旧(作者)

2010-04-28 23:31

<div class="quote">tengzhao201: 经过测试，比楼主的求最大公约数的算法快一倍！</div>// 
// MsClock.h 
// 
 
#ifndef _MS_CLOCK 
#define _MS_CLOCK 
 
#include <Windows.h> 
 
typedef unsigned long u_long; 
 
class MsClock { 
public: 
    MsClock() { 
        ulStart = ::GetTickCount(); 
    } 
 
    void Restart() { 
        ulStart = ::GetTickCount(); 
    } 
 
    u_long Now() { 
        return ::GetTickCount() - ulStart; 
    } 
 
public: 
    static u_long NowAbsolute() { 
        return ::GetTickCount(); 
    } 
 
private: 
    u_long ulStart; 
}; 
 
#endif

赞回复

夜风依旧(作者)

2010-05-04 10:38

<div class="quote">tengzhao201: 经过测试，比楼主的求最大公约数的算法快一倍！</div>最终发现问题不是模运算的问题，而是当数据量超过1个页面甚至多个页面时，我的算法发生缺页中断的频率非常高，所以性能不好，不过数据量小于1个页面时表现良好。

赞回复

夜风依旧的博客

夜风依旧

浏览223646次

文章分类