前段时间叫平姐借本书解解闷，谁知道拿了本超级难的数学性质的书，操。这本书基本上看不懂，只有两地方看得懂，圈和整数分解。圈引出两个东西，floyd圈检测和原位排列。floyd检测就是两个步长不同的遍历，如果有圈存在，那么他们肯定会碰撞。原位排列In-place permuration就是利用排列中圈的存在，像多米诺骨牌那样逐个替换，这个算法可以达到O(N+lnN)，厉害。整数分解是关于Pollard的高概率分解整数，利用了floyd圈检测。p方法用到函数，f(x)=(x^2 +c)mod N， f(f(x))=(x^2 +c)(x^2 +c) + c mod N,此算法的时间复杂度为O(n^(1/4)),下面贴伪代码
------------------------------------------------------------------------------
function factor(N: integer): integer;
var a, b, c, d: integer;
begin
    a := randominteger(0, N-1);
    b := a;
    c := randominteger(0, N-1);
    repeat
        a := (a*a +c) mod N;
        b := (b*b +c)(b*b +c) +c mod N;
        d := gcd(a-b mod N, N);
    until (d<>1);
factor := d;
end;
--------------------------------------------------------------------------------
 上面所说的gcd就是最大公约数，用辗转相除法就能很快解出。下面贴出原位排列的伪代码
--------------------------------------------------------------------------------

for i :=1 to N do
  if p[i] <> i then
       begin
       t := a[i]; k :=i;
       repeat
           j := k; a[j] := a[p[j]];
           k := p[j]; p[j] := j;
       until k = i;
       a[j] := t;
       end;
    end;

Now assume the elements are c1 c2 ... cn c(n+1) .. c2n

In the resulting array (which is a permutation of the original)
The ith element from the original goes to 2i modulo 2n+1.

Thus index 1 goes to 2, 2 goes to 4, 4 goes to 8 ... ultimately comes back to 1 (all working modulo 2n+1)

Note that, it is a permutation which is composed of "cycles" like the ones described above (I think Zekaric made the mistake of assuming there is just one cycle)

For instance consider the case when n=4

1 2 3 4 5 6 7 8

It should become

5 1 6 2 7 3 8 4

so 1 -> 5 -> 7 -> 8 -> 4 -> 2 -> 1 (-> means goes to)
and 3 -> 6 -> 3

So the cycles are (1 5 7 8 4 2) and (3 6)

Assume you had an oracle which told you one element from each cycle. Can you come up with an O(n) time and O(1) space algorithm?

If we do not have such an oracle, trying to come up with elements from distinct cycles becomes hard.

This is where number theory comes in:

In case 2n+1 is a power of 3 = 3^m say, using number theory, we can show that the cycles are exactly

(1, 2, 2^2, ... ) (powers of 2) (In fact these are all the numbers relatively prime to 3^m, note, working modulo 2n+1, i.e modulo 3^m)
(3, 3*2, 3*2^2, ...)  (numbers of the form 3 * 2^j
(3^2, 3^2 *2 ,....) numbers of the form 3^2 * 2^j
...
(3^(m-1),....) numbers of the form 3^(m-1) * 2^j

(will post a proof of this later if someone is interested)

Thus the "number theory oracle" has told us that the powers of 3 are guaranteed to be in different cycles! That is all we need!

So in the special case of 2n+1 being a power of 3, we can give an O(n) time and O(1) space algorithm.

Given the special case (power of 3) algorithm, we can now make this work for any n:

In the O(nlogn) solution I gave above, instead of k = n/2, pick k to be a power of 3 close to n and use the special knowledge of cycles to shuffle that left partial array in O(n) time. Now for the right partial array, we have a new n' = (n-k) and repeat finding a k' which is a power of 3 etc. Overall, time is O(n) and space is O(1).

 

copyrights of all the articles above are belonged to the original owner.
------------------------------------------------------------------------------------------------------------

more details about the maths are ignored. I prefer the first solution, :)