Juggling算法（数组旋转）的时间复杂度为何是线性的？

Great question! Let's break down exactly why this algorithm operates in O(n) linear time, using your code as a reference.

First, let's recall the core idea of the Juggling Algorithm: it splits the array into g = gcd(d, n) independent circular chains (where d is the rotation count, n is the array size). Each chain consists of elements that need to be shifted among themselves to achieve the rotation. For example:

• If n=12 and d=4, gcd(4,12)=4, so we get 4 chains each with 3 elements.
• If n=10 and d=3, gcd(3,10)=1, so the entire array is one single chain.

Now let's analyze the operations count:

• The outer for loop runs exactly g times (once per chain).
• For each chain, the inner while loop processes all elements in that chain. Each chain has n/g elements. Inside the loop, we perform a constant number of operations (calculating k, checking conditions, assigning arr[j] = arr[k]) for every element except the last one, then one final assignment of temp to close the chain. That's a total of n/g operations per chain.

When we sum this up across all chains:
g * (n/g) = n total operations.

Every element in the array is read and written exactly once—no element is processed more than once, and there's no nested loop that adds extra overhead. All operations inside the loops are constant time (O(1)), so the total time complexity simplifies to O(n).

To tie this back to your code:

• The temp = arr[i] initializes the starting element of the chain.
• The while loop cycles through each element in the chain, shifting values forward by d positions (wrapping around with k = k - n when needed).
• Once we loop back to the starting index i, we place the initial temp value in its final position, completing the chain.

Each of these steps contributes to processing one element, and with exactly n such element operations total, the algorithm runs in linear time.

内容的提问来源于stack exchange，提问作者Vijju123