杂耍算法

Question

方法（一种杂耍算法）将数组划分为不同的集合，其中集合数等于n和d的GCD，并在集合内移动元素。如果GCD与上述示例数组（n=7，d=2）一样为1，则元素将仅在一个集合内移动，我们只需从temp=arr[0]开始，并将arr[I d]一直移动到arr[I]，最后将temp存储在正确的位置。

以下是n=12和d=3的示例。GCD为3，且

设arr[]为{1，2，3，4，5，6，7，8，9，10，11，12}

a） 元素首先在第一组中移动–（此移动请参见下图）

排列

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

b） 然后是第二盘。此步骤后的arr[]--

c） 最后是第三盘。此步骤后的arr[]--

/*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）

有人能给我解释一下这个算法是如何工作的以及它的渐近复杂性吗？

Answer 1

杂耍算法

在此方法中，将数组划分为M个集合，其中M=GCD（n， k），然后旋转每个集合中的元素。

从数组的元素数（n）和要对数组进行的旋转数（k），得到块的GCD（n， k）数。然后在每个块中，将发生移位到块中相应的元素。

在移动所有块中的所有元素后，数组将旋转给定次数。

例如：如果我们想将下面的数组旋转2个位置。1 2 3 4 5 6

  M = GCD(6, 2) = 2;
  Initial Array : 1  2  3  4  5  6   
  First Set Moves : 5   2   1   4   3   6
  Second Set Moves : 5   6   1   2   3   4          //  The array is rotated twice.

public class Main
{

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

/*Function to left rotate array of by d number of rotations*/
public static void leftRotate(int arr[], int d, int n) 
{ 
    int i, j, k, temp; 
    for (i = 0; i < gcd(d, n); i++) // gcd(d,n) times the loop will iterate
    { 
        /* move i-th values of blocks */
        temp = arr[i]; 
        j = i; 
        while (true) { 
            k = j + d; 
            if (k >= n) // The element has to be shifted to its rotated position
                k = k - n; 
            if (k == i) // The element is already in its rotated position
                break; 
            arr[j] = arr[k]; 
            j = k; 
        } 
        arr[j] = temp; 
    }} 

//  Main function
public static void main(String[] args) 
{ 
    int arr[] = { 1, 2, 3, 4, 5, 6, 7 }; 
    int no_of_rotations = 2;
    int n = arr.length;
    System.out.println("Array Elements before rotating : "); 
    for(int i = 0 ; i < n ; i++)
    {
        System.out.print(arr[i]+ " "); // Printing elements before rotation
    }
    leftRotate(arr, no_of_rotations, n); 
    System.out.println("\nArray Elements after rotating : "); 
    for(int i = 0 ; i < n ; i++)
    {
        System.out.print(arr[i] + " "); // Printing elements after rotation
} } }

Answer 2

函数中的for循环：

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

将进行exatclygcd（d， n）迭代。现在让我们看看循环内部发生了什么：它需要所有满足：k%gcd（d， n）==i的单元格arr[k]并交换它们。当然有确切的：n/gcd（d， n），这就是函数在循环的一次迭代中将进行多少次交换。因此，函数的整个渐近时间复杂度将是O（gcd（d， n）*n/gcd（d， n））==O（n）。代码的其余部分对时间复杂度没有影响，并且几乎是自我解释的。