, , . , 64- , K64 K32 , , 16, - 48 . . . : , Rj j/2 , Rj.
, . , 50- . 24. , , . .
. 24.
, , N2, N/3 . , , , , .
1959 . . . 25 , 16 . 8 : (R1,R9), (R2,R10), , (R8, R16). . . 25. . : (R1,R5,R9,R13), (R4, R8,R12,R16). . .
. 25. 8, 4, 2, 1
; , 16 . , , .
" ", h, , , h . ht-1,ht-2,,h0, h0 1. , .
|
|
h0,h1, .
N ( 1000), :
ht-1, 3ht>=N
, (h0, h1, h2,)=(1, 5, 19, ), O(N4/3).
, , , , .
, , 1 2, R1 R2, , R2 R3, R3 R4 . . ; , , RN RN-1, RN-2 . ., , , . , , RN , a R1 - . " ", , , "" .
, , , , , .
: O(n2), , .
, .
, - . - . , , k. k, .
. " - ". , , , , . - .