方法（一杂耍算法） 划分阵列中不同集合，其中集合数量是等于n和d GCD并移动内套的元素。 如果GCD为1的是上面的例子阵列（N = 7，D = 2），那么元素将在一个只设置感动，我们刚开始TEMP = ARR [0]，并继续前进ARR [I + D]给Arr [我]，并最终存储温度在正确的地方。

METHOD (A Juggling Algorithm) Divide the array in different sets where number of sets is equal to GCD of n and d and move the elements within sets. If GCD is 1 as is for the above example array (n = 7 and d =2), then elements will be moved within one set only, we just start with temp = arr[0] and keep moving arr[I+d] to arr[I] and finally store temp at the right place.

下面是一个例子N = 12和D = 3 GCD是3和

Here is an example for n =12 and d = 3. GCD is 3 and

让改编[]是{1，2，3，4，5，6，7，8，9，10，11，12}

Let arr[] be {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}

A）的元素首先在第一套移动 - （参见下图的这个动作）

a) Elements are first moved in first set – (See below diagram for this movement)

ArrayRotation

ArrayRotation

      arr[] after this step --> {4 2 3 7 5 6 10 8 9 1 11 12}

B）然后，在第二组。           ARR []这一步后 - > {4 5 3 7 8 6 10 11 9 1 2 12}

b) Then in second set. arr[] after this step --> {4 5 3 7 8 6 10 11 9 1 2 12}

C）最后，在第三盘。           改编[]在此步骤之后 - > {4 5 6 7 8 9 10 11 12 1 2 3}     / *函数来打印一个数组* /     无效printArray（INT改编[]，诠释大小）;

c) Finally in third set. arr[] after this step --> {4 5 6 7 8 9 10 11 12 1 2 3} /* function to print an array */ void printArray(int arr[], int size);

/*Function to get gcd of a and b*/
int gcd(int a,int b);

/*Function to left rotate arr[] of siz n by d*/
void leftRotate(int arr[], int d, int n)
{
  int i, j, k, temp;
  for (i = 0; i < gcd(d, n); i++)
  {
    /* move i-th values of blocks */
    temp = arr[i];
    j = i;
    while(1)
    {
      k = j + d;
      if (k >= n)
        k = k - n;
      if (k == i)
        break;
      arr[j] = arr[k];
      j = k;
    }
    arr[j] = temp;
  }
}

/*UTILITY FUNCTIONS*/
/* function to print an array */
void printArray(int arr[], int size)
{
  int i;
  for(i = 0; i < size; i++)
    printf("%d ", arr[i]);
}

/*Function to get gcd of a and b*/
int gcd(int a,int b)
{
   if(b==0)
     return a;
   else
     return gcd(b, a%b);
}

/* Driver program to test above functions */
int main()
{
   int arr[] = {1, 2, 3, 4, 5, 6, 7};
   leftRotate(arr, 2, 7);
   printArray(arr, 7);
   getchar();
   return 0;
}

时间复杂度：O（N） 辅助空间：O（1）

Time complexity: O(n) Auxiliary Space: O(1)

有人可以请给我这个算法是如何工作的很好的解释和它的渐近复杂性？

Can somebody please give me nice explanation of how this algorithm works and its asymptotic complexity?

推荐答案

for循环的功能：

leftRotate(int arr[], int d, int n)

将会使exatcly GCD（D，N）迭代。现在让我们来看看发生了什么环路内：它需要所有的细胞改编[K] 它满足： K％GCD（D，N） ==我 并交换他们。当然也有完全相同： N / GCD（D，N）其中，这是该函数将有多少掉期使循环的一次迭代。因此，功能的整体时间复杂度将是 O（GCD（D，N）* N / GCD（D，N））==为O（n） 。的code，其余没有对时间复杂度的影响，并为pretty的多的自我explainatory。

is going to make exatcly gcd(d, n) iterations. Now lets look at what is happening inside the loop: it takes all the cells arr[k]which fulfill: k % gcd(d, n) == i and swaps them. Of course there are exactly: n / gcd(d, n) of them and that is how many swaps the function will make in one iteration of the loop. Therefore the whole asymptotic time complexity of the function is going to be O(gcd(d, n) * n / gcd(d, n)) == O(n). The rest of the code does not have an impact on the time complexity and is pretty much self explainatory.