Algorytmy i struktury danych

Prowadzący:

dr hab. inŜ. Kazimierz Worwa, prof. WAT

e-mail:

kworwa@wat.edu.pl

r.a. 2008/2009

WOJSKOWA AKADEMIA TECHNICZNA

Wydział Cybernetyki

Algorytmy i struktury danych

A L G O R Y T M Y I ST R U K T U R Y D A N Y C H

R A ZE M

W ykłady

Ć w iczenia

L aboratoria

30x

20+

Algorytmy i struktury danych

Przedmiot kończy się egzaminem

Warunkiem dopuszczenia do egzaminu jest uzyskanie co najmniej 16 pkt.
z ćwiczeń i zajęć laboratoryjnych (łącznie)

W ramach ćwiczeń rachunkowych student moŜe uzyskać do 10 pkt., w tym:

0 – 5 pkt. z odpowiedzi ustnych i/lub sprawdzianów pisemnych,
wg ustaleń prowadzącego ćwiczenia;

0 – 5 pkt. z kolokwium końcowego;

W ramach ćwiczeń laboratoryjnych student moŜe uzyskać do 20 pkt.;
na kaŜdych ćwiczeniach laboratoryjnych student powinien opracować
(napisać

uruchomić)

program,

będący

rozwiązaniem

zadania

sformułowanego przez prowadzącego zajęcia; za poprawny, napisany w
trakcie zajęć program student otrzymuje 2 pkt.; za kaŜdy poprawny program
oddany z opóźnieniem (na kolejnych zajęciach) student otrzymuje 1 pkt.

Egzamin - test wielokrotnego wyboru

Warunki zaliczenia przedmiotu

Algorytmy i struktury danych

LITERATURA

Aho A.V., Hopcroft J.E., Ullman J.D.: Algorytmy i struktury danych.

Wydawnictwo Helion, Gliwice, 2003.

2. Aho A.V., Hopcroft J.E., Ullman J.D.: Projektowanie i analiza

algorytmów. Wydawnictwo Helion, Gliwice, 2003.

3. Banachowski L., Diks K., Rytter W., Algorytmy i struktury danych.

WNT, Warszawa, 2006.

4. Cormen T.H., Leiserson C.E., Rivest R.L., Stein C.: Wprowadzenie do

algorytmów. WNT, Warszawa, 2005.

5. Drozdek A.: C++. Algorytmy i struktury danych. Wydawnictwo Helion,

Gliwice, 2004.

6. Kotowski P.: Algorytmy + struktury danych = abstrakcyjne typy

danych. Wydawnictwo BTC, Warszawa, 2006.

7. Harris S, Ross J.: Algorytmy od podstaw. Wydawnictwo Helion,

Gliwice, 2006.

8. Wirth N.: Algorytmy + struktury danych = programy. WNT, Warszawa,

2004.

9. Wróblewski P.: Algorytmy, struktury danych i techniki programowania.

Wydawnictwo Helion, Gliwice, 2006.

Algorytmy i struktury danych

Tematyka przedmiotu

Poj

cia podstawowe

Listy

Kolejki (LIFO, FIFO, kolejki priorytetowe)

Drzewa binarne

drzewa BST

drzewa AVL

drzewa czerwono-czarne

drzewa cz

ęś

ciowo uporz

dkowane (kopce)

Drzewa wielokierunkowe

Algorytmy sortowania

wewn

trznego

zewn

trznego

Podstawowe algorytmy grafowe

Tablice rozproszone (haszowanie)

Problemy obliczeniowo trudne

Algorytmy i struktury danych

Materiały do wykładów

Materiały wykorzystywane na wykładach udost

pniam na stronie

http://www.kw.ocom.pl/

folder

Algorytmy i struktury danych

logowanie:

nazwa u

ytkownika

2008/2009

hasło

Algorytmy i struktury danych

Wykład 1-2

Pojęcia podstawowe.
ZłoŜoność obliczeniowa algorytmów.

Algorytmy i struktury danych

Tematyka wykładu

Poj

cia podstawowe

Klasyfikacja algorytmów

Własno

ci algorytmów

Metody oceny algorytmów

Poj

cie zło

ono

ci obliczeniowej algorytmów

Zło

ono

ść

asymptotyczna: O-notacja,

Ω

-notacja,

-notacja

Wyznaczanie zło

ono

ci czasowej algorytmów:

iteracyjnych

rekurencyjnych

Algorytmy i struktury danych

Potoczne rozumienie pojęcia „algorytm”

Algorytmika jest dziedzin

wiedzy zajmuj

badaniem

algorytmów

Potocznie algorytm jest rozumiany jako pewien przepis na
wykonanie zestawu czynno

ci, prowadz

cych do osi

gni

cia

oczekiwanego i z góry okre

lonego celu

Mówi si

równie

algorytm jest pewn

le okre

lon

procedur

obliczeniow

, która dla zestawu wła

ciwych danych

wej

ciowych generuje okre

lone dane wyj

ciowe

Dzisiejsze, uogólnione znaczenie słowa algorytm:

zbiór reguł post

powania, umo

liwiaj

cych rozwi

zanie okre

lonego

zadania w sko

czonej liczbie kroków (w sko

czonym czasie)

Algorytmy i struktury danych

ochodzenie słowa „algorytm”

Słowo „algorytm” pochodzi od łaci

skiego słowa „algorism”,

rozumianego w

redniowieczu jako sztuka rachowania na liczbach

w systemie decymalnym

Słowo „algorism” zostało utworzone od nazwiska perskiego
matematyka z 9-tego wieku n.e., Muhameda ibu-Musy al-Choresmi,
twórcy systemu dziesi

tnego

Algorytmy i struktury danych

Pojęciowy model algorytmu

Algorytm mo

e by

rozumiany jako pewne odwzorowanie

które dla okre

lonego zestawu danych wej

ciowych

generuje okre

lony zestaw danych wyj

ciowych

f: We

Dane

wejściowe

Dane

wyjściowe

Algorytmy i struktury danych

Pojęcie dziedziny algorytmicznej

dy algorytm działa na pewnym zbiorze obiektów (np. liczb),

wykonuj

c na tych obiektach pewne operacje

Zbiór obiektów wraz z operacjami wykonywanymi na tych
obiektach nazywamy dziedzin

algorytmiczn

Algorytmy i struktury danych

posoby zapisu algorytmów

Opis algorytmu obejmuje precyzyjny opis jego kolejnych
kroków

Do przedstawienia algorytmu stosuje si

opis werbalny,

zapis formalny, np.:

zapisy graficzne (schematy blokowe),

formalne specyfikacje programów (np.VDM)

zapisy w postaci pseudokodu (paraprogramu)

zapis algorytmu w dowolnym j

zyku programowania

Algorytmy i struktury danych

Język programowania

zyk programowania jest

rodkiem umo

liwiaj

cym zapis algorytmów w

postaci zrozumiałej dla człowieka, a równocze

nie przetwarzalnej do postaci

zrozumiałej dla komputera.

Zapis algorytmu w j

zyku programowania jest traktowany jako zapis

formalny.

Program komputerowy mo

e by

uznawany za jeden z rodzajów modeli

matematycznych.

Kod źródłowy programu
(w języku programowania)

Kod wynikowy programu
(w języku maszynowym)

Przetworzenie

programu

źródłowego

w kod

maszynowy

Algorytmy i struktury danych

Klasyfikacja algorytmów

Rozwa

dziemy nast

puj

ce klasy algorytmów:

algorytmy sekwencyjne - algorytmy równoległe;

algorytmy numeryczne - algorytmy nienumeryczne;

algorytmy rekurencyjne - algorytmy iteracyjne.

Algorytmy i struktury danych

Techniki algorytmiczne

Podstawowe techniki wykorzystywane w budowie algorytmów:

Iteracja

Rekurencja

Algorytmy i struktury danych

Rekurencja

Rekurencja oznacza wywołanie funkcji (procedury) przez t

sam

funkcj

(procedur

)

Niepo

Ŝą

dana cecha definicji rekurencyjnych: aby wyznaczy

n-t

warto

ść

trzeba najpierw wyznaczy

wszystkie „wcze

niejsze” warto

ne jest, aby kolejne wywołania funkcji (procedury) rekurencyjnej

były realizowane dla kolejnych warto

ci parametrów formalnych w taki

sposób, aby nie doszło do zjawiska „niesko

czonej p

tli

rekurencyjnych wywoła

funkcji”

Algorytmy i struktury danych

Stos programu w wywołaniach

rekurencyjnych – przykład C/C++

Adres powrotu do

systemu operacyjnego

Dno stosu programu

Adres powrotu z funkcji

Zwracana wartość

Parametry przez adres

Parametry przez wartość

Zmienne lokalne

Adres powrotu z funkcji

Zwracana wartość

Parametry przez adres

Parametry przez wartość

Zmienne lokalne

Adres powrotu z funkcji

Zwracana wartość

Parametry przez adres

Parametry przez wartość

Zmienne lokalne

funkcja main()

funkcja f1

funkcja f2

funkcja fN

Kolejne poziomy rekurencji wymagają

odkładania na stosie programu kolejnych

rekordów aktywacji funkcji

Stos programu w wywołaniach

rekurencyjnych jest bardziej

eksploatowany niŜ wtedy, gdy wywołania

nie są rekurencyjne

Algorytmy i struktury danych

Funkcja rekurencyjna – ciąg Fibonacciego

n-ty wyraz ci

gu Fibonacciego jest wyliczany wg formuły, n

≥

dla n<2

Fib(n)=

Fib(n-2) + Fib(n-1) dla n>=2

Rekurencyjna implementacja w j

zyku C:

long int Fib (int n)

{

if (n<2)

return n;

else

return Fib(n-2) + Fib (n-1);

}

Dla duŜych n stos programu
„nie wytrzyma” takiej realizacji
funkcji Fib!

Algorytmy i struktury danych

Efektywność rekurencyjnego wykonania funkcji

Fibonacciego (cd.)

Rekurencyjna implementacja funkcji Fibonacciego jest bardzo nieefektywna.

Stos programu nie jest praktycznie w stanie zrealizowa

tego algorytmu ju

dla liczb wi

kszych od 50.

Oznacza to,

e program ma zbyt du

Ŝą

„zło

ono

ść

pami

ciow

”.

F(6)

F(5)

F(4)

F(2)

F(0)

F(1)

F(3)

F(1)

F(2)

F(3)

F(1)

F(2)

F(4)

F(2)

F(3)

F(0)

F(1)

F(0)

F(1)

F(0)

F(1)

F(2)

F(0)

F(1)

Przykład: drzewo wywoła

dla F(6):

Algorytmy i struktury danych

Efektywność rekurencyjnego wykonania funkcji Fibonacciego

2 692 537

1 346 268

242 785

121 392

21 891

10 945

1 973

986

177

Liczba

wywoła

Liczba

dodawa

Algorytmy i struktury danych

Iteracyjne wykonanie rekurencyjnej funkcji

Fibonacciego

Bardziej efektywna jest iteracyjna implementacja funkcji Fibonacciego. Nie
przepełniamy wtedy stosu programu i wykonujemy znacznie mniejsz

liczb

przypisa

warto

ci ni

w implementacji rekurencyjnej

Przykład iteracyjnej implementacji funkcji Fibonacciego:

long int IteracyjnyFib(int n)
{

return n;

else {

for ( ; i<=n; i++) {

tmp = current;
current += last;
last = tmp;

}

return current;

}

Algorytmy i struktury danych

Efektywność iteracyjnego wykonania rekurencyjnej funkcji

Fibonacciego

2 692 537

242 785

21 891

1 973

177

Liczba przypisa

(wywoła

) w algorytmie

rekurencyjnym

Liczba przypisa

algorytmie iteracyjnym

Program 1.1b

Program 1.1a

Algorytmy i struktury danych

Pułapki rekurencji

int jakas_funkcja(int n)
{

if (n==1)

return 1;

else

if ((n%2)==0)

// czy n jest parzyste?

return jakas_funkcja(n-2)*n;

else

return jakas_funkcja(n-1)*n;

}

Program 1.2

Co będzie wynikiem wykonania poniŜszej funkcji?

Algorytmy i struktury danych

Jak porównywać algorytmy?

Idealny algorytm to taki, który:

ma czytelny i zrozumiały kod,
jest napisany w ogólnie dostępnym języku programowania,
jest efektywny obliczeniowo (szybko liczy, nie wymaga duŜej pamięci),
zawsze daje poprawne wyniki.

Algorytmy i struktury danych

Jak porównywać algorytmy – przykładowe kryteria

prostota,

czytelność kodu,

długość kodu,

poprawność,

czas realizacji (obliczeń),

zajętość pamięci.

Algorytmy i struktury danych

Częściowa poprawność algorytmu

Specyfikacją algorytmu nazywamy parę warunków (własności):

Warunek początkowy

Warunek końcowy

< wp , wk >

Algorytm A wykorzystujący strukturę danych S jest częściowo poprawny ze
względu na specyfikację <wp, wk>, jeŜeli dla wszystkich danych spełniających
warunek początkowy i dla których algorytm zatrzyma się, uzyskane wyniki
spełniają warunek końcowy.

Algorytmy i struktury danych

Całkowita poprawność algorytmu

Mówimy, Ŝe algorytm A wykorzystujący strukturę danych S jest całkowicie
poprawny ze względu na specyfikację <wp, wk> jeŜeli dla wszystkich
danych w strukturze S spełniających warunek początkowy wp, algorytm
zatrzymuje się i daje wyniki spełniające warunek końcowy wk.

Algorytmy i struktury danych

ZłoŜoność obliczeniowa - miara słuŜąca do porównywania efektywności

algorytmów. Mamy dwa zasadnicze kryteria efektywności: czas i pamięć.

Do oceny efektywności stosujemy jednostki logiczne, wyraŜające

związek miedzy rozmiarem danych n (np. wielkość pliku lub tablicy)
a ilością czasu T potrzebną na ich przetworzenie.

ZłoŜoność obliczeniowa algorytmów

Algorytmy i struktury danych

Rodzaje złoŜoności obliczeniowej algorytmów

Zło

ono

ść

pami

ciowa - wyra

ana w skali zaj

ci pami

ci (PAO,

pami

ci zewn

trznej), niezb

dnej dla realizacji algorytmu

Zło

ono

ść

czasowa - wyra

ana w skali czasu wykonania algorytmu

(liczba kroków, czas rzeczywisty)

Na ogół (obecnie) zło

ono

ść

czasowa jest wa

niejsza od zło

ono

pami

ciowej

Algorytmy i struktury danych

Czynniki wpływające na czas wykonania programu

Rozmiar danych wej

ciowych algorytmu

Jako

ść

kodu wynikowego generowanego przez kompilator (j

zyk

kodu

ródłowego)

Architektura i szybko

ść

komputera, na którym program jest

wykonywany

Efektywno

ść

wykorzystanego algorytmu (jego zło

ono

ść

czasowa)

Algorytmy i struktury danych

ZłoŜoność czasowa algorytmu

Definicja

Zło

ono

ść

czasowa to liczba operacji podstawowych, wykonanych

przez algorytm w czasie jego realizacji, wyra

ona jako funkcja rozmiaru

danych.

Oznaczenie

Zło

ono

ść

czasowa algorytmu A jako funkcja rozmiaru danych n:

lub

Algorytmy i struktury danych

ZłoŜoność czasowa algorytmu

Do oszacowania czasu realizacji algorytmu nie powinno si

ywa

zwykłych jednostek czasu

Zamiast tego powinny by

stosowane jednostki logiczne, okre

laj

zwi

zek mi

dzy rozmiarem danych wej

ciowych a czasem

potrzebnym na ich przetworzenie

Funkcje opisuj

ce zwi

zek mi

dzy

T(n)

mog

bardzo zło

one;

w praktyce upraszczamy je, pozostawiaj

c tzw. składowe dominuj

ce,

tj. składowe maj

ce najwi

kszy wpływ na warto

T(n)

Algorytmy i struktury danych

Przykład

Niech zale

ść

czasu realizacji algorytmu od rozmiaru

danych wej

ciowych opisuje funkcja

f(n) = n

+ 100n + log

n + 1000

Algorytmy i struktury danych

Porównanie szybkości wzrostu funkcji

f(n)= log n

f(n)=n

f(n) = 2

f(n) = n

f(n)

Algorytmy i struktury danych

Funkcja: f(n) = n

+ 100*n + log

n + 1000

n f(n) n

100*n log

n 1000

1 101 0.1% 9% 0.0 % 91%

10 2 101 4.8% 48% 0.05% 48%

100 21 002 48% 48% 0.001% 4.8%

1 101 003 91% 9% 0.0003%

0.09%

99% 1% 0.0%

0.001%

99,9% 0.1% 0.0%

0.0000%

Szybkość wzrostu poszczególnych składników funkcji

Dla duŜych wartości n składnikiem dominującym jest n

, tzn. funkcja rośnie

jak n

; pozostałe składniki mogą być pominięte;

n – ilość wykonywanych operacji

Algorytmy i struktury danych

Funkcja wyraŜająca zaleŜność miedzy n a T jest zwykle bardzo
skomplikowana, a jej dokładne obliczenie ma znaczenie jedynie w
odniesieniu do specyficznych problemów

PrzybliŜoną miarą efektywności najczęściej stosowaną w praktyce jest tzw.
asymptotyczna złoŜoność obliczeniowa.

Asymptotyczna złoŜoność obliczeniowa

Algorytmy i struktury danych

O-notacja

Definicja:

Funkcja

f(n)

jest funkcj

o zło

ono

O(g(n)),

eli istniej

takie

liczby dodatnie

e dla ka

dego

zachodzi

Zgodnie z powy

definicj

, zwi

zek mi

dzy funkcjami

na wyrazi

stwierdzaj

g(n)

jest kresem górnym dla

f(n)

Uwaga

: powy

sza definicja nie daje

adnych wskazówek co do

tego, jak wyznaczy

stałe

(takich par mo

e by

wiele)

Interpretacja:

O(g(n)) = { f(n): istniej

dodatnie liczby c i n

takie,

e dla

dego n

≥

zachodzi 0

≤

f(n)

≤

c g(n) }

Piszemy: f(n)

∈

O(g(n)) lub cz

ęś

ciej f(n) = O(g(n))

≥

g(n)

f(n)

≤

Algorytmy i struktury danych

O-notacja – ilustracja graficzna

f(n)

c g(n)

(n)=O(g(n))

Algorytmy i struktury danych

Przykład

Niech zale

ść

czasu realizacji algorytmu od rozmiaru

danych wej

ciowych n opisuje funkcja

f(n) = n

+ 100n + log n + 1000

Wówczas, wykorzystuj

c O-notacj

, mo

na napisa

+ 100n + log n + 1000

∈

O(n

2 )

Zatem, dla badanej funkcji

T(n) = n

Tak okre

lona zło

ono

ść

czasow

algorytmu nazywa si

asymptotyczn

zło

ono

czasow

W praktyce wykorzystuje si

tak

e poj

cia optymistycznej,

pesymistycznej oraz

redniej zło

ono

ci czasowej algorytmu

Algorytmy i struktury danych

Własności O-notacji

Własność 1 (przechodniość)

Jeśli f(n) jest O(g(n)) i g(n) jest O(h(n)), to f(n) jest O(h(n)).

Własność 2:

Jeśli f(n) jest O(h(n)) i g(n) jest O(h(n)), to f(n)+g(n) jest O(h(n)).

Własność 3:

Funkcja an

jest O(n

Własność 4:

Funkcja n

jest O(n

k+j

) dla dowolnego nieujemnego j.

Z powyŜszych własności wynika, ze dowolny wielomian jest „wielkie O” dla n
podniesionego do najwyŜszej w nim potęgi, czyli

f(n) = a

+ a

k-1

+ ... + a

jest O(n

)

(jest teŜ oczywiście O(n

k+j

) dla dowolnego nieujemnego j).

Algorytmy i struktury danych

Własność 5:

Jeśli f(n)=c g(n), to f(n) jest O(g(n))

Własność 6:

Funkcja log

n jest O(log

n) dla dowolnych a i b większych niŜ 1

Własność 7:

log

n jest O(log

n) dla dowolnego dodatniego a

Własności O-notacji (cd.)

Wniosek:

Wszystkie funkcje logarytmiczne (niezaleŜnie od podstawy logarytmu) są

sobie równowaŜne w sensie O-notacji

Algorytmy i struktury danych

Własności O-notacji (cd.)

Własność 8 (reguła sumy)

(n)=O(f(n))

(n)=O(g(n))

czasami wykonywania dwóch

fragmentów algorytmu, to ł

czny czas wykonania obydwu fragmentów

wynosi:

(n) +T

(n) = O(max{ f(n), g(n)})

Własność 9 (reguła iloczynu)

Niech

(n)=O(f(n))

(n)=O(g(n))

czasami wykonywania dwóch

fragmentów algorytmu. Wówczas:

(n)

⋅

(n) = O(f(n)

⋅

g(n))

Algorytmy i struktury danych

Jedną z najwaŜniejszych funkcji przy ocenianiu efektywności algorytmów
jest funkcja logarytmiczna.

JeŜeli moŜna wykazać, Ŝe złoŜoność algorytmu jest rzędu logarytmicznego,
algorytm moŜna traktować jako bardzo dobry.

Istnieje wiele funkcji lepszych w tym sensie niŜ logarytmiczna, jednak
zaledwie kilka spośród nich, jak O(log

log

n) czy O(1) ma praktyczne

znaczenie.

Własności O-notacji

Algorytmy i struktury danych

Ω

- notacja

O-notacja dotyczy kresu górnego funkcji

Istnieje symetryczna definicja kresu dolnego w postaci

Ω

-notacji

Definicja:

f(n)

jest funkcj

o zło

ono

eli istniej

takie liczby

dodatnie

e dla ka

dego

zachodzi

Wniosek

Funkcja f(n)

ma zło

ono

ść

wtedy i tylko wtedy, gdy

g(n)

ma zło

ono

ść

≥

g(n)

f(n)

≥

(g(n))

Ω

(f(n))

(g(n))

Ω

Algorytmy i struktury danych

Ω

- notacja

Interpretacja:

Ω

(g(n)) = { f(n): istniej

dodatnie liczby c i n

takie,

e dla

dego n

≥

zachodzi 0

≤

c g(n)

≤

f(n) }

Piszemy: f(n)

∈ Ω

(g(n)) lub cz

ęś

ciej f(n) =

Ω

(g(n))

Algorytmy i struktury danych

Ω

-notacja – ilustracja graficzna

f(n)

c g(n)

f(n)=

Ω

(g(n))

Algorytmy i struktury danych

- notacja

Definicja

f(n)

jest funkcj

o zło

ono

eli istniej

liczby dodatnie

, c

takie,

e dla ka

dego

zachodzi

Wniosek

Funkcja

f(n)

ma zło

ono

ść

wtedy i tylko wtedy, gdy

f(n)

ma zło

ono

ść

f(n)

ma zło

ono

ść

(g(n))

≥

g(n)

f(n)

g(n)

≤

(g(n))

Ω

Algorytmy i struktury danych

- notacja

Interpretacja:

(g(n)) = { f(n): istniej

dodatnie liczby c

, c

i n

takie,

e dla

dego n

≥

zachodzi 0

≤

g(n)

≤

f(n)

≤

g(n) }

Piszemy: f(n)

∈ Θ

(g(n)) lub cz

ęś

ciej f(n) =

(g(n))

Algorytmy i struktury danych

-notacja – ilustracja graficzna

g(n)

f(n)=

(g(n))

f(n)

g(n)

Algorytmy i struktury danych

O-notacja,

Ω

-notacja,

-notacja – porównanie

f(n)

c g(n)

f(n)=

Ω

(g(n))

f(n)

c g(n)

(n)=O(g(n))

g(n)

f(n)=

(g(n))

f(n)

g(n)

Algorytmy i struktury danych

Notacja asymptotyczna - podsumowanie

Niech f , g : N

→

Mówimy, Ŝe funkcja f jest co najwyŜej rzędu g, jeśli
(

∃

c>0,

∃

∈

∀

n>n

f(n)

≤

c g(n)

Mówimy, Ŝe funkcja f jest co najmniej rzędu g, jeśli
(

∃

c>0,

∃

∈

∀

n>n

c g(n)

≤

f(n)

f =

Ω

(g )

f = O (g )

f =

(g )

Mówimy, Ŝe funkcja f jest rzędu g, jeśli
(

∃

>0, c

>0,

∃

∈

∀

n>n

g(n)

≤

f(n)

≤

g(n)

Algorytmy i struktury danych

Porównanie szybkości wzrostu funkcji

Mówimy, Ŝe algorytm A ma złoŜoność czasową:

logarytmiczną

jeśli T(A, n) =

(log n)

liniową

jeśli T(A, n) =

(n)

kwadratową

jeśli T(A, n) =

)

wielomianową

jeśli T(A, n) =

)

α ∈

wykładniczą

jeśli T(A, n) =

) a

∈

Algorytmy i struktury danych

Porównywanie rzędów funkcji

Przykład 1

Niech f(n)=100n, g(n)= 2n+100, h(n) = 0.1 n

Mamy: f = O(n), f =

Ω

(n), g = O(n) ale takŜe g = O(n

), g =

(n)

h = O(n

), h

≠

O(n), h =

Ω

(n)

Lemat (o porównywaniu rz

dów funkcji)

Niech lim

→∞

f(n)/g(n) = c. Wówczas:

1. Je

eli c

≠≠≠≠

0 to f i g s

tego samego rz

du.

2. Je

eli c = 0, to f = O(g) oraz f

≠≠≠≠ Ω

Ω

(g).

3. Je

eli c =+

∞

, to f ma rz

d wi

kszy ni

g = O(f) i g

≠≠≠≠ Ω

Ω

(f).

Przykład 2

f(n) = 0,3 n

+ 10n + 100

g(n)= n

h(n) = log n

lim

→∞

f(n)/g(n)= 0,3

Zatem f = g =

)

lim

→∞

f(n)/h(n) = +

∞

Zatem h = O(f) = O(n

≠ Ω

(f).

Algorytmy i struktury danych

ZłoŜoność a rozmiar i czas

Jaki jest maksymalny rozmiar problemu n, który moŜna rozwiązać w
ustalonym czasie, znając złoŜoność algorytmu?

Ile czasu potrzeba na rozwiązanie zadania o ustalonym rozmiarze i złoŜoności?

1 s

1 godz.

lg n

n lg n

15* 10

1000000

63*10

36*10

13* 10

60* 10

T(A,n)

czas

n=10

n= 10

lg n

n lg n

dni

6.6

13.3

0.6ms

0.1ms

10ms

lat

10ms

0.1s

100s

100

lat

T(A,n)

wymiar

Algorytmy i struktury danych

Czy szybkość moŜe przezwycięŜyć złoŜoność?

Mamy 5 algorytmów A

, A

rozwiązujących ten sam problem.

Niech s

oznacza maksymalny rozmiar problemu, który moŜna rozwiązać na

komputerze 1 przy pomocy algorytmu A

w ustalonym czasie t.

Jaki jest maksymalny rozmiar problemu, który moŜna rozwiązać w tym

samym czasie t na komputerze 2, który jest 10 razy szybszy?

Komputer 1

Komputer 2

lg n

2*s

10*s

√

10*s

3,2 + s

⋅

Zatem:

czyli

x = 3,2 + s

)

(

Szukamy takiego x, Ŝe

)

(

Dla komputera 2:

)

(

Dla komputera 1:

Algorytmy i struktury danych

Wpływ dziesięciokrotnego przyspieszenia

komputera na wzrost rozmiaru zadania

1,3

2,3

3,2

10,0

100

100n

Wzgl

dny przyrost

rozmiaru problemu

Komputer

dziesi

ciokrotnie

szybszy

Komputer

oryginalny

Zło

ono

ść

czasowa T(n)

Algorytmy i struktury danych

Wyznaczanie złoŜoności czasowej - przykłady

Przykład 1

Pojedyncza pętla wyznaczająca sumę elementów wektora

for (i=sum=0; i<n; i++)

sum=sum+ a[i];

Liczba przypisań w całej pętli: 2+2n

ZłoŜoność czasowa: T(n)=O(n)

Algorytmy i struktury danych

Wyznaczanie złoŜoności czasowej - przykłady

Przykład 2

Pętla podwójna wyznaczająca sumę elementów tablicy

for (i=0; i<n; i++) {

for (j=1, sum=a[0]; j<=i; j++)

sum=sum+ a[j];

printf(„\n Suma podtablicy %d” , sum)

}

Liczba przypisań w całej pętli:

ZłoŜoność czasowa: T(n)=O(n

)

(

)

(

)

...

(

−

∑

−

Algorytmy i struktury danych

Wyznaczanie złoŜoności czasowej - przykłady

Przykład 3

erowanie elementów tablicy leŜących na i pod główną przekątną

int tab[n][n];

void zerowanie();

{

int i,j;

i=0;

// 1

while (i<n)

// 1

{

j=0;

// 1

while (j<=i)

// 1

{

tab[i][j]=0; // 1
j=j+1;

// 1

}
i=i+1;

// 1

}

ZłoŜoność czasowa (z uwagi na wszystkie instrukcje):

)

(

)

(

))

(

)

(

)

(

∑

−

Algorytmy i struktury danych

Kiedy algorytm zawiera rekurencyjne wywołanie samego siebie, jego czas

działania moŜna często opisać zaleŜnością rekurencyjną (rekurencją),
wyraŜającą czas dla problemu rozmiaru n za pomocą czasów dla
podproblemów mniejszych rozmiarów.

MoŜemy więc uŜyć narzędzi matematycznych, aby rozwiązać rekurencję

i w ten sposób otrzymać oszacowania czasu działania algorytmu.

ZłoŜoność czasowa algorytmów rekurencyjnych

Algorytmy i struktury danych

Rekurencja odpowiadającą czasowi działania algorytmu typu “dziel

i zwycięŜaj” opiera się na podziale jednego poziomu rekursji na trzy etapy

Niech

T(n)

będzie czasem działania algorytmu dla problemu rozmiaru

Jeśli rozmiar problemu jest odpowiednio mały, powiedzmy

≤≤≤≤

dla pewnej

stałej

, to jego rozwiązanie zajmuje stały czas, co zapiszemy jako

(1)

ZałóŜmy ze dzielimy problem rozmiaru

podproblemów, kaŜdy rozmiaru

n/b

Jeśli

D(n)

jest czasem dzielenia problemu na podproblemy, a

C(n)

czasem

scalania rozwiązań poszczególnych podproblemów w pełne rozwiązanie
problemu wyjściowego , to otrzymujemy rekurencję

Rekurencja dla algorytmu typu “dziel i zwycieŜaj”

dla

C(n)

D(n)

aT(n/b)

)

(

)

(

≤







Algorytmy i struktury danych

Przykład: algorytm sortowania przez scalanie

znajdujemy środek przedziału, zajmuje to czas stały D(n)=

(1)

rozwiązujemy rekurencyjnie dwa podproblemy, kaŜdy rozmiaru

n/2, co daje czas działania 2 T(n/2)

łączymy dwa uporządkowane podciągi w jeden (uporzadkowany) w czasie

(n), a wiec C(n)=

(n).

Ostatecznie

MoŜna pokazać, Ŝe rozwiązaniem tej rekurencji jest T(n) =

(n log n)

Rekurencja dla algorytmu typu “dziel i zwycieŜaj”

dla

(n)

)

(

2T(n/2)

)

(

)

(







Algorytmy i struktury danych

Metody rozwiązywania rekurencji:

Metoda podstawiania: zgadujemy oszacowanie, a następnie
wykorzystujemy indukcję matematyczną.

Metoda iteracyjna: przekształcamy rekurencję na sumę (korzystamy
z technik ograniczania sum).

Metoda drzewa rekursji: uzupełniająca metodę podstawiania

Metoda rekurencji uniwersalnej: stosujemy oszacowanie na rekurencje
mające postać

T(n) = a T(n/b) + f(n),

gdzie a

≥

1, b>1, a f(n) jest daną funkcją.

Wyznaczanie złoŜoności czasowej algorytmów rekurencyjnych

Algorytmy i struktury danych

Metoda podstawiania:

Polega na odgadnięciu postaci rozwiązania, a następnie wykazaniu przez

indukcję, Ŝe jest ono poprawne.

Trzeba takŜe znaleźć wartości odpowiednich stałych.

Metoda jest bardzo skuteczna, ale moŜe być stosowana tylko w przypadkach,

kiedy moŜna przewidzieć postać rozwiązania.

Wyznaczanie złoŜoności czasowej algorytmów rekurencyjnych

Algorytmy i struktury danych

Przykład:

Postać rekurencji: T(n) = 2T(



n/2



) + n

Zachodzi: T(1)=1; T(2)=4; T(3)=5, T(4)=12 ...

Przewidywane rozwiązanie: T(n) = O(n lg n), tzn.

T(n)

≤

c n lg n

ZałoŜenie: dla n =



n/2



zachodzi: T(



n/2



)

≤



n/2



lg (



n/2

 )

Indukcja: T(n)

≤

2[c



n/2



lg (



n/2



)] + n

≤

c n lg(n/2) + n

c n lg n – c n lg 2 + n

c n lg n – cn + n

≤

c n lg n

Zatem, jeśli c

≥≥≥≥

1 zachodzi:

T(n)

≤≤≤≤

c n lg n

Rozwiązanie T(n) = O(n lg n) jest poprawne dla c

≥

2 i n

≥

Metoda podstawiania

Dlaczego?

Oznaczenia:



 - największa liczba całkowita x taka, Ŝe x<a



 - najmniejsza liczba całkowita x taka, Ŝe x>a

∃

Dlaczego?

Algorytmy i struktury danych

Metoda iteracyjna

Polega na rozwijaniu (iterowaniu) rekurencji i wyraŜanie jej jako sumy

składników zaleŜnych tylko od warunków brzegowych.

Następnie mogą być uŜyte techniki sumowania do oszacowania rozwiązania.

Metoda iteracyjna

Algorytmy i struktury danych

Rozwinięcie rekurencji

Jest uproszczoną wersją metody iteracyjnej

Polega na:

rozpisaniu równania rekurencyjnego dla kolejnych wartości

dodaniu otrzymanych równań stronami,

zredukowaniu jednakowych wyrazów i przekształceniu otrzymanej
zaleŜności tak, aby uzyskać jawną zaleŜność funkcji

T(n)

Metoda jest skuteczna jedynie w odniesieniu do niektórych postaci rekurencji

Wyznaczanie złoŜoności czasowej algorytmów rekurencyjnych

Algorytmy i struktury danych

Metoda iteracyjna – rozwinięcie rekurencji

Przykład 1.

Funkcja Silnia

int Silnia(int n) {

if (n==0)

return 1;

else

return n*silnia(n-1);

}







≥

−

dla

)

(

dla

)

(

Zło

ono

ść

czasowa

Czas wykonania jednej instrukcji
porównania wartości (ogólnie:

(1)

Algorytmy i struktury danych

)

(

)

(

)

(

...

)

(

)

(

)

(

)

(

−

)

(

)

(

...

)

(

)

(

)

(

...

)

(

)

(

−

Zatem:

T(n)= n+1=O(n)

Metoda iteracyjna - rozwinięcie rekurencji







≥

−

dla

)

(

dla

)

(

Przykład 1 (cd.)

dodajemy stronami

Algorytmy i struktury danych

Przykład 2:

Postać rekurencji: T(n) = 3T(n/4) + n; T(1)=a

Iterujemy: T(n) = n + 3T(n/4) =

= n + 3[n/4 +3T(n/16)] =

= n + 3 n/4 + 9T( n/16) =

= n + 3 n/4 + 9[ n/16 + 3T(n/16)] =

= n + 3 n/4 + 9 n/16 + 27 T(n/64) = ...

Metoda iteracyjna

)

(

)

(

...

T(n)

log

≤

∑

Iterujemy tak długo, aŜ osiągniemy warunek brzegowy:

i-ty składnik ciągu wynosi 3

n/4

Iterowanie kończymy, gdy n/4

= 1, czyli i = log

≠

−

Algorytmy i struktury danych

Drzewo rekursji pozwala w dogodny sposób zilustrować rozwijanie

rekurencji, jak równieŜ ułatwia stosowanie aparatu algebraicznego, słuŜącego
do rozwiązywania tej rekurencji

Szczególnie uŜyteczne gdy rekurencja opisuje algorytm typu “dziel

i zwycięŜaj

”

KaŜdy węzeł drzewa reprezentuje czas wykonania podproblemu
Sumując czasy na kolejnych poziomach drzewa otrzymujemy czas łączny
Drzewo rekursji moŜe stanowić pomoc przy odgadywaniu rozwiązania

(w metodzie podstawienia)

Metoda drzewa rekursji

Algorytmy i struktury danych

T(n) = 2 T(n/2) + n

, T(1)=a

T(n/2)

T(n) =

)

Zatem, ostateczny wynik:

T(n/4)

(n/2)

T(n/4)

w sumie:

)

Drzewo rekursji

Przykład 1

...

Jaką maksymalną wysokość ma drzewo rekursji?

...

Algorytmy i struktury danych

T(n) =

(n log n )

Zatem, ostateczny wynik:

T(n) = T(n/3) + T(2n/3) + n, T(1)=a

n/9

2n/9

n/3

2n/3

2n/9

4n/9

log

3/2

wysokość drzewa: log

3/2

Drzewo rekursji

Przykład 2

Dlaczego?

w sumie:

⋅

log

3/2

...

Algorytmy i struktury danych

Metoda rekurencji uniwersalnej

Metoda rekurencji uniwersalnej podaje “uniwersalny przepis” rozwiązywania

równania rekurencyjnego postaci

T(n) = a T(n/b) + f(n)

gdzie a

≥

1 i b>1 są stałymi, a f(n) jest funkcją asymptotycznie dodatnią.

Za wartość n/b przyjmujemy najbliŜszą liczbę całkowitą (mniejszą lub

większą od wartości dokładnej) tj. n/b =n/b lub n/b = n/b

Algorytmy i struktury danych

Rekurencja opisuje czas działania algorytmu, który dzieli problem

rozmiaru

problemów, kaŜdy rozmiaru

n/b

, gdzie

są

dodatnimi stałymi.

KaŜdy z

problemów składowych jest rozwiązywany rekurencyjnie

w czasie

T(n/b)

Koszt dzielenia problemu oraz łączenia rezultatów częściowych jest

opisany funkcją

f(n)

Dowód twierdzenia o rekurencji uniwersalnej:

patrz: T.H. Cormen, Ch.E.Leiserson, R.L.Rivest , C Stein: Wprowadzenie do algorytmów

Metoda rekurencji uniwersalnej

Algorytmy i struktury danych

Niech

≥

b>1

będą stałymi, niech

f(n)

będzie pewną funkcją i niech

T(n)

będzie zdefiniowane rekurencyjnie, dla nieujemnych liczb całkowitych:

T(n) = a T(n/b) + f(n),

gdzie

n/b

oznacza najbliŜszą liczbę naturalną (mniejszą lub większą od

wartości dokładnej) tj.

n/b =n/b

lub

n/b = n/b

Wtedy funkcja

T(n)

moŜe być ograniczona asymptotycznie w następujący

sposób:

1. Jeśli

dla pewnej stałej

, to

2. Jeśli to

3. Jeśli

dla pewnej stałej

i jeśli

a f(n/b)

≤≤≤≤

c f(n)

dla pewnej stałej

c<1

i wszystkich dostatecznie duŜych

, to

T(n) =

(f(n))

Metoda rekurencji uniwersalnej

)

(

)

(

log

)

(

)

(

log

−

)

(

)

(

log

)

log

(

)

(

log

)

(

)

(

log

Ω

Algorytmy i struktury danych

Interpretacja

W kaŜdym z trzech przypadków porównujemy funkcję

f(n)

z funkcją

Rozwiązanie rekurencji zaleŜy od większej z tych dwóch funkcji

Jeśli funkcja jest większa (Przypadek 1), to rozwiązaniem rekurencji

jest

Jeśli funkcja

f(n)

jest większa (Przypadek 3), to rozwiązaniem jest

T(n) =

(f(n))

Jeśli funkcje są tego samego rzędu (Przypadek 2), to rozwiązaniem jest

czyli

T(n) =

( f(n) log n)

Metoda rekurencji uniwersalnej

log

)

log

(

)

(

log

)

(

)

(

log

Algorytmy i struktury danych

Przykład 1

Określić oszacowanie asymptotyczne dla rekurencji:

T(n) = 9 T(n/3) + n

Mamy:

a=9

b=3

f(n)=n

, a zatem

PoniewaŜ

, gdzie

, moŜemy zastosować przypadek 1

twierdzenia o rekurencji uniwersalnej i wnioskować Ŝe rozwiązaniem jest

T(n) =

( n

)

Metoda rekurencji uniwersalnej

log

)

(

)

(

log

−

Algorytmy i struktury danych

Przykład 2

Określić oszacowanie asymptotyczne dla rekurencji:

T(n) = T(2n/3) + 1

Mamy:

a=1

b=3/2

f(n)=1

, a zatem

Stosujemy przypadek 2, gdyŜ

a zatem rozwiązaniem rekurencji jest

Metoda rekurencji uniwersalnej

log

)

(

)

(

)

(

)

(

)

(

log

)

(log

)

log

(

)

log

(

)

(

log

Algorytmy i struktury danych

Przykład 3

Określić oszacowanie asymptotyczne dla rekurencji:

T(n) = 3T(n/4) + n log n

Mamy:

a=3

b=4

f(n)=n log n

, a zatem

PoniewaŜ

, gdzie

~ 0.2

, więc stosuje się tutaj przypadek

3, jeśli moŜemy pokazać, Ŝe dla

f(n)

zachodzi warunek regularności

Dla dostatecznie duŜych

moŜemy napisać:

a f(n/b) = 3 (n/4) log (n/4)

≤

(3/4) n log n = c f(n), przy czym c=¾ < 1

Warunek regularności jest zatem jest spełniony i moŜemy napisać, Ŝe

rozwiązaniem rekurencji jest

T(n) =

[f(n)] =

(n log n)

Metoda rekurencji uniwersalnej

793

log

)

(

)

(

log

Ω

Algorytmy i struktury danych

Przykład 4

Określić oszacowanie asymptotyczne dla rekurencji:

T(n) = 2T(n/2) + n log n

Mamy:

a=2

b=2

f(n)=n log n

, a zatem

Wydaje się, Ŝe powinien to być przypadek 3, gdyŜ

f(n)=n log n

jest

asymptotycznie większe niŜ (ale nie wielomianowo!)

Stosunek jest asymptotycznie mniejszy niŜ

dla

kaŜdej dodatniej stałej

W konsekwencji rekurencja ta “wpada” w lukę między przypadkiem 2 i 3.

Nie moŜna zatem zastosować twierdzenia o rekurencji uniwersalnej

Metoda rekurencji uniwersalnej

log

)

(

log

Algorytmy i struktury danych

Zadanie

Wykorzystując metodę rekurencji uniwersalnej określić oszacowanie

asymptotyczne dla rekurencji:

a) T(n) = 2 T(n/2) + n

b) T(n) = T(2n/3) + 1

Algorytmy i struktury danych