i

5.2. . .

5.4 , , , -. .
-, Ω(Nlog N): , .
. (ͲͲ Ҳ). N . , .
ͲҲ Ҳ '.
{x1, ..., xN } N {x1, ..., xN } EN. W EN ͲͲ Ҳ {x1, ..., xN } ( W , - ). , W N '. ij, - p {x1, ..., xN } EN.


, , p. Wπ ', #(W) = N!.
:
. - , , N , Ω(Nlog N) .

.

1. Ѳ
² o(1) Ѳ
N x1 ,, xN. x, q, .( ). , x (x, 0). 򳺿 , .
5.2. Ω(log N) ( ).
, ', , q - N - 1 , x, 5.2 - .

2. k- ѲIJ
Ѳ k- ѲIJ.
k- ѲIJ, , k = 1, Ѳ k- ѲIJ. 5.2 k- ѲIJ.

3. ײ .1-.4.
5.5 ( ).

5.6


.5.5. ' , .
3.1. ͲͲ Ҳ N .
{ x1 ,, xN }. y = 0, ({x1 ,..., xN} N { (x1, 0), , (xN, 0) }). , , , (d = 0 "Ͳ", d 0 ""). , , k, .
3.2. N Ѳ ײ Ѳ.
N Ѳ ײ Ѳ , , ' , (N) .
3.3. N (.3).
N , .
3.4. N .
N {x1 ,, xN}. x (x, 0) ({x1 , ..., xN} N { (x1,0),, (xN,0) }), .

: (1,2), (2,3), (3,4), (4,5) (O(N)) (1, 2,3 4, 5,...)

, x xj, ' x xj . ' , N - 1 (i, j), . x, (N).
3.5. N вֲ(.4).
N {x1, , xN}, 5.6. N-1 , ({x1 ,, xN} N { (x1, 0),, (xN-1 , 0), (xN , -a)}). . , , xi, (N) . Ω(Nlog N) .


. 5.6. ' вֲ.

. N вֲ , S , S.
, ͲͲ Ҳ N Ω(Nlog N), .
5.3 - , ' : , , вֲ, Ѳ ײ Ѳ, Ω(Nlog N) .

i