Метод сдваивания

1.

Метод сдваивания
• Каскадная схема
a1
Tp n / 2 (n) c log 2 n
S p n / 2
a2
a1+a2
n 1
( n)
1
E p n / 2 ( n)
log 2 n
log 2 n
a3
a4
a3+a4
a1+a2+a3+a4
a5
a6
a7
a5+a6
a8
a7+a8
a5+a6+a7+a8
a1+a2+a3+a4+a5+a6+a7+a8
• Модифицированная каскадная схема
T
S
p
n
log2 n
p
n
log2 n
(n) 2 c log 2 n
( n)
n 1
2 log 2 n
2
1
E
p
n
log2 n
( n)
1
2
X1 X2 X3 X4
X5 X6 X7 X8
X9 X1 0 X1 1 X1
2
X1 3 X1 4 X1 5 X1
1
6