Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
26
1.Podstawowezasadyanalizyalgorytmów
więcej,liczbawykonańinstrukcjiiteracyjnejjestrównaliczbiedzieleńcałkowitychprzez
2,czylidługościbinarnejn.Dlan>0mamyzatem
W(n)=A(n)=
L
logn
J
+1=logn+O(1)
Δ(n)=δ(n)=0
(rozmiaremdanychjestn,aoperacjądominującądzieleniecałkowiteprzez2).Widzimy,że
wtymprzypadkudowodzenieskończonościdziałaniainstrukcjiiteracyjnejjestpowiązane
zeznajdowaniempesymistycznejzłożonościczasowej.
JakoprzykładalgorytmurekurencyjnegorozważmyalgorytmEuklidesaznajdowanianaj-
większegowspólnegodzielnikadwóchdodatnichliczbnaturalnych.
functionNWD(x,y:integer):integer;
varr:integer;
begin{O:x>0∧y>0}
r:=xmody;
ifr=0thenNWD:=yelseNWD:=NWD(y,r)
{β:NWD=(x,y)}
end;
Przez(x,y)oznaczyliśmynajwiększywspólnydzielnikdodatnichliczbnaturalnychxiy.
PoprawnośćfunkcjiNWDwzględempodanychwarunkówpokazujemy,dowodząc,żedla
każdychdodatnichwartościnaturalnychxiyobliczeniewywołaniafunkcjiNWD(x,y)
kończysięzwartościąNWD=(x,y).Stosujemyindukcjęwzględemwartościy.Zakładając
poprawnośćdlawszystkichz,0<z<y,otrzymujemy,żegdyxmody=0,wówcza(x,y)=y,
natomiastwprzeciwnymprzypadkumożemyzastosowaćzałożenieindukcyjnedlapary(y,
xmody)iwewnętrznegowywołaniarekurencyjnego.Wtedy(x,y)=(y,xmody).
1.5.
Podstawowestrukturydanych
Poniżejrozważamypodstawowestrukturydanych:listę,graf,zbióridrzewo,wpro-
wadzającpotrzebnewdalszejczęściksiążkioznaczeniaiomawiającpodstawowemetody
implementacjitychstruktur.Będziemyzakładać,żeelementywchodzącewskładrozważa-
nychstrukturdanychpochodzązpewnegoniepustegouniwersumU.Jakwiadomozzasad
programowaniastrukturalnego,zagadnieniadotyczącebudowysamejstrukturydanychijej
użyciawalgorytmiewygodniejestrozważaćoddzielnie.
