Pseudokody do wykladu 1
24 luty 2011
Przyklad 1: Wartość wyrażenia an
POTEGA (a, n)
b �! 1
k �! n
while k = 0
8
do b �! b " a
k �! k - 1
return b
POTEGA-BINARNA (a, n)
b �! 1
k �! n
c �! a
while k = 0
8
do if (k mod 2)=0
then c �! c " c
k �! k div 2
else b �! b " c
k �! k - 1
return b
Typeset by AMS-TEX
1
2
Przyklad 3: Dany jest wektor A[1..n]. Wyznaczyć najmniejszy
indeks i skladowej o wartości x (wyszukiwanie liniowe)
ELEMENT-1 (A, n, x)
i �! 1
while (A[i] = x) and (i = n)
8 8
do i �! i + 1
if A[i] = x
8
then drukuj komunikat
else return i
Przyklad 4: Rozważmy wektor A[1..n + 1] i wstawmy w A[n + 1]
element x (,,wartownik )
ELEMENT-2 (A, n, x)
A[n + 1] �! x
i �! 1
while A[i] = x
8
do i �! i + 1
if i d" n
then return i
else drukuj komunikat
3
Twierdzenie 1 (o rekurencji uniwersalnej)
Niech a e" 1 i b > 1 be da stalymi, niech f(n) be dzie pewna funkcja
i niech T (n) bedzie zdefiniowane dla nieujemnych liczb calkowitych
przez rekurencje
T (n) = aT (n/b) + f(n),
gdzie n/b interpretujemy jako #n/b# lub #n/b #. Wtedy T (n) może
być ograniczona asymptotycznie w naste puja cy sposób.
1. Jeśli f(n) = O(nlogb a-�) dla pewnej stalej � > 0, to
T (n) = Ś(nlogb a)
2. Jeśli f(n) = Ś(nlogb a), to
T (n) = Ś(nlogb a lg n)
3. Jeśli f(n) = &!(nlogb a+�), dla pewnej stalej � > 0 oraz
af(n/b) d" cf(n)
dla pewnej stalej c < 1 i dostatecznie dużych n, to
T (n) = Ś(f(n))