procesor
3
1 2
4
4 5
7
10 8
3
11
2
1
9
6
czas
C
max
procesor
3
2
8
4
4 5
1
10
3
11 7
2
1
9
6
czas
C
max
3
2
8 10
5
9
1
7
4
11
6
Lista=(3,2,8,10,5,1,9,7,11,4,6)
procesor
4
3
2
1
2
8 10
5
9
1
7
4
11
6
Lista=(3,2,8,10,5,1,9,7,11,4,6)
procesor
3
4
3
2
1
8 10
5
9
1
7
4
11
6
Lista=(3,2,8,10,5,1,9,7,11,4,6)
procesor
3
4
2
3
2
1
10
5
9
1
7
4
11
6
Lista=(3,2,8,10,5,1,9,7,11,4,6)
procesor
3
4
2
3
8
2
1
5
9
1
7
4
11
6
Lista=(3,2,8,10,5,1,9,7,11,4,6)
procesor
3
4
2
3
8
2
1
10
9
1
7
4
11
6
Lista=(3,2,8,10,5,1,9,7,11,4,6)
procesor
3
4
2
3
5
8
2
1
10
9
7
4
11
6
Lista=(3,2,8,10,5,1,9,7,11,4,6)
procesor
3
4
2
3
5
8
2
1
1
10
7
4
11
6
Lista=(3,2,8,10,5,1,9,7,11,4,6)
procesor
3
9
4
2
3
5
8
2
1
1
10
4
11
6
Lista=(3,2,8,10,5,1,9,7,11,4,6)
procesor
3
9
4
2 7
3
5
8
2
1
1
10
4
6
Lista=(3,2,8,10,5,1,9,7,11,4,6)
procesor
3
9
4
2 7
3
5
11
8
2
1
1
10
6
Lista=(3,2,8,10,5,1,9,7,11,4,6)
procesor
3
9
4
2 7
3
5
11
8
2
1
4
1
10
Lista=(3,2,8,10,5,1,9,7,11,4,6)
procesor
3
9
4
2 7
6
3
5
11
8
2
1
4
1
10
11
6
2
3 9 5
1
4
10 8 7
Lista=(11,6,2,3,9,1,5,4,10,8,7)
procesor
4
3
2
1
6
2
3 9 5
1
4
10 8 7
Lista=(11,6,2,3,9,1,5,4,10,8,7)
procesor
11
4
3
2
1
2
3 9 5
1
4
10 8 7
Lista=(11,6,2,3,9,1,5,4,10,8,7)
procesor
11
4
6
3
2
1
3 9 5
1
4
10 8 7
Lista=(11,6,2,3,9,1,5,4,10,8,7)
procesor
11
4
6
3
2
2
1
9 5
1
4
10 8 7
Lista=(11,6,2,3,9,1,5,4,10,8,7)
procesor
11
4
6
3
2
2
1
3
5
1
4
10 8 7
Lista=(11,6,2,3,9,1,5,4,10,8,7)
procesor
11
4
6
3
2
2
1
3
9
5
4
10 8 7
Lista=(11,6,2,3,9,1,5,4,10,8,7)
procesor
11
4
6
3
2 1
2
1
3
9
4
10 8 7
Lista=(11,6,2,3,9,1,5,4,10,8,7)
procesor
11
4
5
6
3
2 1
2
1
3
9
10 8 7
Lista=(11,6,2,3,9,1,5,4,10,8,7)
procesor
11
4
5
6
3
2 1
2
1
3 4
9
8 7
Lista=(11,6,2,3,9,1,5,4,10,8,7)
procesor
11
4
5
6
3
2 1
10
2
1
3 4
9
7
Lista=(11,6,2,3,9,1,5,4,10,8,7)
procesor
11
8
4
5
6
3
2 1
10
2
1
3 4
9
Lista=(11,6,2,3,9,1,5,4,10,8,7)
procesor
11
8
4
5
6
3
2 1 7
10
2
1
3 4
9
 {Aµ}
µ > 0 Aµ
µ K(x) x " X
|KAµ - K"| d" µK",
K" K KAµ
K Aµ
 Aµ
N(I)
1/µ

1
T IME(Aµ) = O p(N(I)) · e ,
µ
p e

1
Aµ O n2 · 2µ
 Aµ
N(I) 1/µ

1
T IME(Aµ) = O p N(I), ,
µ
p

n3
Aµ O
µ2
 P 2||Cmax
J = {J1, J2, . . . , Jn} n n " Z+
J1, . . . , Jn
pj, j = 1, . . . , n Jj pj " R+
x" = {x1, x2, . . . , xn}
xj " {0, 1} xj = 0 Jj
xj = 1 j = 1, . . . , n
Cmax = max{Cj} - min,
j"J
Cj Jj j = 1, . . . , n
n k
pj p1 e" p2 e" . . . e" pn L
k 1 d" k d" n L
(n - k)
 O(n log n)
O(2k)
xk = {x1, . . . , xk}
k
xk k
xk = {0, 0, . . . , 0} xk
xk = {1, 1, . . . , 1}
Cmax
2k
O(n - k)
O(n log n + 2k)
1/2
µ = ,
1 + k/2
x x
x
1
µ <"
k
k
k = O(1)
µ
ëÅ‚ öÅ‚
1
ìÅ‚ ÷Å‚
íÅ‚ Å‚Å‚
O n log n + 2µ .
 P 2||Cmax
O(n·S)
n
S = pj
j=1
n k
P 2||Cmax

pj
pj = j = 1, . . . , n.
Ü
k
 O(n)
S
O(n · )
k
O(n)
S
O(n · ) < O(nS)
k
2nk
µ = ,
S
µ <" k
k

µS
k =
2n
S
O(n · )
k
ëÅ‚ öÅ‚
n2
ìÅ‚ ÷Å‚
ìÅ‚ ÷Å‚
ìÅ‚ ÷Å‚
O .
íÅ‚ Å‚Å‚
µ
"
"
"
"
"
P = NP

"
"
"
"
"
"
"
"