Złożoność obliczeniowa - Zadania 2.pdf
(
75 KB
)
Pobierz
381400878 UNPDF
Algorytmy i programowanie – 8
Zło»ono±¢obliczeniowa
Relacja
Niech
f
(
n
) i
g
(
n
) b¦d¡ funkcjami rozbiegaj¡cymi do niesko«czono±ci gdy
n
!1
.
Mówimy,
»e funkcja
f
(
n
) ro±nie wolniej ni»
g
(
n
)
,
co zapisujemy
f
(
n
)
g
(
n
) wtedy i tylko wtedy gdy
lim
n
!1
f
(
n
)
g
(
n
)
= 0
.
Notacjaasymptotyczna
Dla danej funkcji
g
(
n
) oznaczamy:
•
(
g
(
n
)) =
{
f
(
n
) :
9
c
1
,c
2
9
n
0
takie, »e
8
n
n
0
0
¬
c
1
g
(
n
)
¬
f
(
n
)
¬
c
2
g
(
n
)
}
•
O
(
g
(
n
)) =
{
f
(
n
) :
9
c
9
n
0
takie, »e
8
n
n
0
0
¬
f
(
n
)
¬
cg
(
n
)
}
•
(
g
(
n
)) =
{
f
(
n
) :
9
c
9
n
0
takie, »e
8
n
n
0
0
¬
cg
(
n
)
¬
f
(
n
)
}
Fakt
Dla ka»dych dwóch funkcji
f
(
n
) i
g
(
n
) zachodzi zale»no±¢
f
(
n
) = (
g
(
n
)) wtedy i tylko
wtedy, gdy
f
(
n
) =
O
(
g
(
n
)) i
f
(
n
) = (
g
(
n
))
.
Twierdzenieorekurencjiuniwersalnej
Niech
a
1 i
b
1 b¦d¡ stałymi,
f
(
n
) b¦dzie pewn¡ funkcj¡ a
T
(
n
) b¦dzie zdefiniowane dla
nieujemnych liczb całkowitych przez rekurencj¦:
T
(
n
) =
aT
n
b
+
f
(
n
)
gdzie
b
oznacza
b
lub
b
.
Wtedy funkcja
T
(
n
) mo»e by¢ ograniczona asymptotycznie w
nast¦puj¡cy sposób:
n
log
b
a
−
n
log
b
a
•
je±li
f
(
n
) =
O
n
log
b
a
dla pewnej stałej
>
0
,
to
T
(
n
) =
,
•
je±li
f
(
n
) =
n
log
b
a
+
,
to
T
(
n
) =
n
log
b
a
ln
n
,
dla pewnej stałej
>
0 oraz je±li
af
b
¬
cf
(
n
) dla pewnej
stałej
c <
1 i wszystkich dostatecznie du»ych
n,
to
T
(
n
) = (
f
(
n
))
.
•
je±li
f
(
n
) =
Zadania
1.
Uszeregowa¢ poni»sze funkcje według relacji
:
n
2
,
53
p
n,
log
n, n
!
,
1
,
p
n,
log
10
n,
2
n
, n
n
2.
Korzystaj¡c z metody rekurencji uniwersalnej podaj oszacowania asymptotyczne dla poni»-
szych rekurencji:
a)
T
(
n
) = 9
T
n
3
+
n
b)
T
(
n
) = 4
T
n
4
2
n
3
+
n
+
n
2
e)
T
(
n
) = 3
T
n
3
+
n
ln
n
f)
T
(
n
) = 4
T
n
2
+
n
3
3.
Czas działania algorytmu
A
jest opisany przez rekurencj¦
T
(
n
) = 7
T
n
2
+ 1
+
n
2
,
a konku-
rencyjnego algorytmu
A
0
przez
T
0
=
aT
0
n
4
+
n
2
.
Jaka jest najwi¦ksza liczba całkowita
a,
przy
której
A
0
jest asymptotycznie szybszy ni»
A
?
4.
Algorytm sortowania przez zliczanie działa na trzech tablicach
n
elementowych:
A
[1
..n
]
zawieraj¡cej nieposortowany ci¡g,
B
[1
..n
]
,
w której zwracany jest posortowany ci¡g elementów
z
A
oraz pomocniczej tablicy
C
[1
..k
]
.
Istotnym zało»eniem jest, »e elementy w tablicy
A
s¡
wszystkie ró»ne i ze zbioru
{
1
,
2
,...,k
}
procedure
SortowaniePrzezZliczanie(
A,B,n,k
)
for
i
1
to
k
do
C
[
i
]
0
for
i
1
to
n
do
C
[
A
[
i
]]
1
for
i
2
to
k
do
C
[
i
]
C
[
i
] +
C
[
i
−
1]
for
i
1
to
n
do
B
[
C
[
A
[
i
]]]
A
[
i
]
a) Oszacowa¢ zło»ono±¢ tego algorytmu.
b) Opracowa¢ wersj¦ tego algorytmu, gdy dopu±cimy powtórzenia w tabeli
A.
c)
T
(
n
) =
T
d)
T
(
n
) = 4
T
n
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