. 1959 . ,
. ,
. ,
,
,
. i -
,
hi,
. hi (,
2^ t, 2^ t -1,,2,1), (
- ),
.
.
.
h1=6 h2=3, h3=2, h4=1
, .
,
.
,
h1, h2,..., h t. [14] ,
: h(i-1)=3h(i)+1, h(t)=1, t=(log3n) -1.
. ,
43.
[14]. ,
h(i) O (n log2 n) O (n 1,2 ).
.
,
, .
( ).
, , . ,
R2 R1 (
).
.
.
|
|
(, )
,
,
.
.
R1.
R1. , O (n)
, ,
R 1.
() ,
.
. ,
. ai, ai/2,
2 i 2 i +1. ,
, .
, :
ai ,
(a (I) >= a (i)). , ,
, (
). ,
.
D1 D2.
D1 D2 ,
. a
D1 D2 , , a
, ,
D1 D2. ,
,
. , n / 2 ,
log n
O (n log n). ,
O (n).
13, 11, 23, 10, 12, 18, 30,
8, 7, 6, 15, 21. ()
, .
()
. , ( )
.
|
|
, .
,
O (1) .
R1 ( ),
, R 1.
,
O (log n).
,
.
: a(i)=<a(2i) a(i)=<a(2i+1), i=1,2,,n/2
:
1. , - O (n).
2. i (i = n, n -1,...,1)
,
, 1
. - O (n log n)
.
R1 R2 R2 ()
R1 (). ,
.