Złożoność obliczeniowa - Zadania 1.pdf
(
55 KB
)
Pobierz
381400877 UNPDF
1Zło»ono±¢obliczneniowa
Zad.1
Korzystaj¡c z twierdzenia o rekurencji uniwersalnej podaj oszacowanie asymp-
totyczne dla:
T
(
n
) = 4
T
(
n/
4) +
n
T
(
n
) = 2
T
(
n/
3) +
n
T
(
n
) = 6
T
(
n/
4) +
n
2
T
(
n
) = 2
T
(2
n
) +
n
T
(
n
) = 3
T
(
n/
3) +
n
log(
n
)
Zad.2
Napisz pseudokod operacji kolejki priortetowej (INSERT, MAXIMUM, EXTACT-
MAX) dla zwykłej kolejki (zaimplementowanej dla tablicy). Mo»na korzysta¢ z
procedur ENQUEUE i DEQUEUE. Oszacuj zło»ono±¢ obliczeniow¡ operacji.
Zad.3
Napisz pseudokod procedury
INSERT
(
Q,i,key
), która b¦dzie wstawiała na
i
-tej pozycji kolejki warto±¢
key
. Operacja ma si¦ odbywa¢ bez nadpisywania
»adnego z elementów (oraz bez zmieniania kolejno±ci). Oszacuj złozono±¢ obli-
czeniow¡ takiej operacji.
Zad.4
Napisz pseudokod funkcji
EXTRACT
(
Q,i
), która b¦dzie usuwała element z
i
-tej pozycji kolejki oraz zwracała jego warto±¢. Oszacuj złozono±¢ obliczeniow¡
operacji.
2Sortowanie
Zad.5
Algorytmy sortowania QUICKSORT i MERGESORT to algorytmy typu dziel
i zwyci¦»aj. Który z nich ma mniejszy koszt scalania, dlaczego?
Zad.8
Wykonaj algorytm PODZIAL n
a poni»szej tabeli.
3 4 9 2 5 1 4 6
procedure
PODZIAL (
A,p,r
)
x
A
[
r
]
i
p
−
1
for
j
p
to
r
−
1
doif
A
[
j
]
¬
x
then
i
i
+ 1
A
[
i
]
$
A
[
j
]
A
[
i
+ 1]
$
A
[
r
]
return
i
+ 1
1
Zad.9
Zmodyfikuj algorytm BUBBLE-SORT tak aby sortował nierosn¡co.
for
i
1
to
n
dofor
j
n
downto
i
+ 1
doif
A
[
j
]
<A
[
j
−
1]
then
A
[
j
]
$
A
[
j
−
1]
3Kopce
Zad.11
Czy lista posortowana malej¡co jest kopcem typu MAX. Dlaczego?
Zad.12
Czy lista posortowana rosn¡co jest kopcem typu MAX. Dlaczego?
Zad.13
Czy ci¡g elementów jest kopcem typu MAX.
a) 21
,
15
,
19
,
9
,
10
,
11
,
12
,
5
,
4
,
1
,
6
,
2
,
4
b) 21
,
15
,
19
,
12
,
15
,
11
,
12
,
5
,
4
,
1
,
6
,
2
,
4
c) 21
,
15
,
19
,
8
,
15
,
11
,
12
,
9
,
4
,
1
,
6
,
2
,
4
Zad.14
Co stanie si¦ z pierwszym el. tabeli je±li wywołamy HEAPIFY(A,1)?
a) 7
,
25
,
19
,
19
,
20
,
11
,
12
,
6
,
14
,
11
,
16
,
2
,
4
MAX-HEAPIFY(
A,i
)
l
LEFT(
i
)
r
RIGHT(
i
)
if
(
l
¬
heap
-
size
[
A
])
and
(
A
[
l
]
>A
[
i
])
then
L
l
else
L
i
if
(
r
¬
heap
-
size
[
A
])
and
(
A
[
r
]
>A
[
L
])
then
L
r
if
L
6
=
i
then
A
[
i
]
$
A
[
L
]
MAX-HEAPIFY(
A,L
)
2
Plik z chomika:
allbe
Inne pliki z tego folderu:
Złożoność obliczeniowa - Zadania 1.pdf
(55 KB)
Złożoność obliczeniowa - Zadania 2.pdf
(75 KB)
złożoność obliczeniowa algorytmu Maszyny Turinga.pdf
(581 KB)
Inne foldery tego chomika:
Dokumenty
Galeria
Prywatne
silent scream niemy krzyk
WCY
Zgłoś jeśli
naruszono regulamin