n n " Z+
cji, i, j " {1, . . . , n}, i = j i j

cji = cij, cji " R+
Ä„"
n-1

T C(Ą") = cĄ (j)Ą"(j+1) + cĄ (n)Ą"(1) - min .
" "
j=1
n cij i, j " {1, . . . , n}
Ä„ Ä„"
T C
Przykładowa instancja PK
2
n = 5
c12(= c21) = 9
c23 = 4
c25 = 10
1 c13 = 7
3
c34 = 6
c14 = 6 c35 = 8
c45 = 10
5
4
Przykładowe rozwiązanie Ą1 instancji PK
Ä„1 = < 1, 2, 5, 4, 3 >
2
c12 = 9
c23 = 4
c25 = 10
1 c13 = 7
3
c34 = 6
c14 = 6 c35 = 8
c45 = 10
5
4
TC(Ä„1) = 9 + 10 + 10 + 6 + 7 = 42
RozwiÄ…zanie Ä„2
Ä„2 = < 1, 3, 2, 5, 4 >
2
c12 = 9
c23 = 4
c25 = 10
1 c13 = 7
3
c34 = 6
c14 = 6 c35 = 8
c45 = 10
5
4
TC(Ä„2) = 37 < TC(Ä„1) = 42
A = {a1, a2, . . . , an} n n " Z+
sj, j = 1, . . . , n aj sj " Z+
wj, j = 1, . . . , n aj wj " Z+
B
A Ä…" A

T S = sj d" B
j"A

T W = wj - max .
j"A
n A sj wj j = 1, . . . , n
A
T W T S
n = 5 A = {a1, a2, a3, a4, a5}
j
sj
wj
B = 10
A = {a2, a3, a4},

sj = 9 d" B = 10,
j"A

wj = 12.
j"A
 1|rj|Cmax
J = {J1, J2, . . . , Jn} n n " Z+
J1, . . . , Jn
pj, j = 1, . . . , n Jj pj " R+
rj, j = 1, . . . , n Jj rj " R+ *" {0}
Ä„"
Cmax = max{CÄ„ (j)} - min,
"
j"J
CĄ (j) = SĄ (j) + pĄ (j)
" " "
j Ą" SĄ" = max{CĄ" , rĄ" }
(j) (j-1) (j)
Ä„"(j) CÄ„" = 0 j = 1, . . . , n
(0)
 X
 A
fA(N(I)) = max{t : t
I
N(I) A
N(I) = n
( )
fA(N(I))
N(I)
fA
O(·) f(n) O(g(n))

0 d" f(n) d" c · g(n),
c,N ne"N
f(n)
- c n ",
g(n)
n " f(n) g(n)
f(n) O(g(n))
n2 - 2n + 5 O(n2)
1 n
n · Ä„ log O(n log n)
2 2
n
1
nĄ log 2 O(nlog n)
2
23n-8 O(2n)
n! - 100n25 + 0, 3n0,3 O(n!)
 1µs
fA(n) n
O(n)
O(n2)
O(n5)
O(n10)
O(2n)
O(3n) 108 1013
O(n!) 1016 1032 1048 1966
fA(n)
O(n) n1 1000·n1
O(n2) n2 31, 62·n2
O(n5) n3 3, 98·n3
O(n10) n4 1, 99·n4
O(2n) n5 n5+10
O(3n) n6 n6+6
n7+3 n7 d" 10
O(n!) n7 n7+2 10 < n7 d" 30
n7+1 30 < n7 d" 1000
 f(n) O(p(n)) p(n)
n O(n) O(n2) O(n log n)
f(n)
p(n) O(2n) O(nlog n) O(n!)
P ‚" NP
NP - ‚" NP P )"NP - = "
klasa NP
klasa P
probl. NP-trudne
probl. silnie NP-trudne
probl.  otwarte
"
"
"
"
"
"
"
"