f (n) = 2lg n!

f (n) = O nlg n + n5
1
f (n) = Ś lg n!
2

nn+3
f (n) = O n = 0

n2
f : N R+ *" {0} f (n) = n lg n2

1
f (n) = O � f (n) + c c 103
n

"
f n2 = &! ( n � f (n))
f (n) = O (c � f (n) + c) c
A T (A, n) = n2 n
K
64 4 TK (A, 64) = 4
TK (A, 512) = 512
TK (A, 1024) = 1024
16 K
256

Alg1 Alg2 A (Alg1, n) = O (n lg n)

W (Alg1, n) = &! n2 T (Alg2, n) = Ś (n lg n)

T (Algorytm, n) = O n2

A (Algorytm, n) = O n3

W (Algorytm, n) = &! n2 lg n



" N >
< sqr (i) = i2




sqr sqr (i) =def (i + 1)

" N
<

p = 2i
p = 2i '" result = p
result = 2n+1 - 1
root

int
root
root

root


n2
O (n lg n)
n
"
&! ( n)

108 107




n2 O (n)
104


104


5, 4, 7, 3, 9, 8, 2,



n
n e" 1

A W (Sortuj, n) =

O n2
A A (Sortuj, n) =
O (n lg n)
S (Sortuj, n) = O (lg n)
T
n

T O n2 lg n
T O (n)
T &! (n lg n)

0, 1, 0, 2, 0, 2, 4, 1, 1, 0, 2,

4, 3, 3, 0, 1
4, 7, 10, 10, 11
0, 4, 6, 10, 10


6

((((1 + ((2 + 3) � 4)) + 5) + 6) + 7)


15

3

Źempty (q) �! Źempty (out (out (in (q, first (q)))))
empty (q) �! in (out (in (q, e)) , f) = out (in (in (q, e) , f))
empty (q) �! Źempty (in (q, e))

member (delete (insert (d, e) , e) , e)
e = f �! delete (insert (d, e) , f) = delete (insert (d, f) , e)

Źmember (delete (delete (insert (d, e) , e) , e) , e)
(A, h) m d
E |E| = n h
e " E
W (member (d, e) , m, n) = O (n)

n
A (insert (d, e) , m, n) = O
m
W (delete (d, e) , m, n) = O (m + n)
T
5, 3, 4, 7, 6
T 5
T 4, 3, 6, 5, 7
4 T

T n d

member d O (lg n) T
insert d &! (lg n) T
delete d &! (lg n) T

e = min(pq) �! delmin (insert (pq, e)) = insert (delmin (insert (pq, e)) , e)

delmin (insert (pq, e)) = pq �! Źempty(pq)
e = min (pq) �! min (insert (pq, e)) = e


H 5, 4, 3, 2, 1, 6, 7

5, 3, 2, 6, 7, 4, 1
delmin (H) delmin (H)
3, 5, 6, 7, 4
delmin H

H n T

"
T lg( n)
T n = 1000
T
2lg n-1
ą = 3, 1, 4, 2, 5
ą
[1, 2, 4, 3, 5]
ą
[1, 2, 3, 5, 4]
ą
[1, 2, 4, 3, 5]
E = {a, b, c, d, e} U

init (E)
find (U, a)
union (U, find (U, d) , find (U, e))
find (U, e)
union (U, find (U, e) , find (U, a))
union (U, find (U, b) , find (U, c))

find (U, e) = find (U, d)
find (union (U, find (U, a) , find (U, b)) , c) = find (U, e)
find (U, c) = find (U, d)
G = (V, E) V = {1, 2, 3, 4, 5, 6}

G


G



O n2 n
G


G


G
G

G

Ł = { }










"
n n
&! (n lg n)



P NP


NP