杂耍算法

Question

方法(一种杂耍算法)将数组划分为不同的集合，其中集合数等于n和d的GCD，并在集合内移动元素。如果GCD为1，如上面的例子数组(n = 7，d =2)，那么元素将只在一个集合内移动，我们只需从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[]后这一步--> {4 5 3 7 8 6 10 11 9 1 2 12}。

c)最后在第三组.arr[]这一步之后--> {4 5 6 7 8 9 10 11 12 1 2 3} *打印数组的函数 * 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) O(1)

谁能给我好好解释一下这个算法的工作原理和它的渐近复杂度？

Answer 1

函数中的for循环。

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

将会使特别是 gcd(d, n) 迭代。现在让我们看看在循环中发生了什么：它把所有的单元格的 arr[k]其中满足。k % gcd(d, n) == i并将其交换。当然正好有。n / gcd(d, n) 的，这就是函数在一次循环迭代中的交换次数。因此整个函数的渐进时间复杂度将是 O(gcd(d, n) * n / gcd(d, n)) == O(n). 其余的代码对时间复杂度没有影响，几乎可以自圆其说。

Answer 2

杂耍算法

在这种方法中，将数组划分为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
} } }