Algorytmy i struktury danych – wykład 1 Strona: 1

Algorytmy i struktury danych

Wstęp

Przedmiotem kursu są struktury danych i algorytmy. Struktura

danych (ang. Data structure) to sposób reprezantacji danych w pamięci komputera (na dysku).

Struktury danych to między innymi tablice, listy wiązane, stosy, kolejki, drzewa binarne, kopce, drzewa n-tego stopnia, tablice asocjacyjne (mapy), grafy skierowane i nieskierowane.

Algorytmy (ang. Algorithm) służą do manipulacji na strukturach danych, np. algorytmy sortowania danych, wyszukiwania

określonych elementów.

Wykorzystując wiedzę z dziedziny algorytmów i struktur danych można będzie rozwiązywać problemy, które dotyczą trzech

zagadnień:

Przechowywanie danych ze świata zewnętrznego

Tworzenia narzędzi programisty

Modelowania rozwiązań

Przechowywanie danych ze świata zewnętrznego

Wiele struktur danych i technik, które poznamy dotyczy

sposobów przechowywania i obsługi danych ze świata

zewnętrznego. Na przykład kartoteka osobowa zawiera dane

rzeczywiście istniejących osób, katalog książek opisuje wykaz książek w bibliotece, a rekord transakcji finansowej dotyczy np.

rzeczywistej faktury za kupowane towary.

Nie-komputerowym przykładem przechowania danych ze

świata zewnętrznego jest zbiór kart katalogowych, które mogą

być użyte na różne sposoby. Jeśli karty zawierają dane: imię, nazwisko, adres i telefon to mamy książkę adresową. Jeśli

zawierają opis książki to otrzymujemy katalog książek.

Jeśli chcemy zamienić jakiś zbiór kart na program, trzeba

rozważyć następujące problemy:

Jak przechować dane w pamięci komputera

Algorytmy i struktury danych – wykład 1 Strona: 2

Czy wybrana metoda sprawdzi się dla stu kart?, dla

tysiąca?, dla miliona?.

Czy wybrana metoda pozwala szybko dodawać nowe karty

i usuwać stare?

Czy pozwala szybko wyszukać określoną kartę?

Jak efektywnie uporządkować karty alfabetycznie?

Narzędzia programisty

Nie wszystkie struktury są używane tylko do przechowywania

danych ze świata zewnętrznego. Niektóre struktury są

projektowane aby ułatwić wykonywanie pewnych zadań

programowi. Programista używa takich struktur jako narzędzi

do wykonywania pewnych operacji. Listy, stosy, kolejki i kolejki priorytetowe często są używane właśnie w ten sposób.

Modelowanie danych ze świata zewnętrznego

Pewne struktury modelują bezpośrednio sytuacje ze świata

zewnętrznego. Najważniejszą strukturą tego typu jest graf.

Można użyć grafu do reprezentowania tras samolotów między

miastami, połączeń w obwodzie elektrycznym lub zadań w

dużym projekcie.

Kolejka lub kolejka priorytetowa może służyć jako model ciągu osób czekających do okienka w banku lub ciąg zadań

czekających do obsłużenia przez system operacyjny w

komputerze.

Struktury danych w bibliotece Javy

Pakiet klas java.util zawiera struktury danych takie jak Vector (rozszerzalna tablica), Stack (stos), Dictionary (słownik) czy Hashtable (tablica asocjacyjna).

Aby można było z nich skorzystać należy pamiętać o dodaniu

wiersza:

Import java.util.*;

Algorytmy i struktury danych – wykład 1 Strona: 3

W naszym kursie ignorujemy istnienie tych wbudowanych klas.

Celem naszym jest poznanie podstaw organizacji i zasad

działania struktur danych.

Mając taką wiedzę, decyzję, czy tworzyć własne klasy, czy użyć gotowych, programista może podjąć samodzielnie.

Algorytm

Algorytm to opis procesu obliczeniowego w sformalizowanym

języku, o precyzyjnie określonej semantyce

Język zapisu algorytmu =

abstrakcyjny model komputera

Przykłady modeli:

• model matematyczny

maszyna Turinga, automat niedeterministyczny ze stosem,

...

• abstrakcyjna maszyna cyfrowa

RAM – Random Access Memory machine

• język programowania wysokiego poziomu(np. C++, Java)

Przykład:

Dana jest tablica A[n] n - liczb.

Posortuj ją niemalejąco.

Algorytm 1:

sortowanie bąbelkowe, zakodowany w asemblerze, wykonuje

3n2 operacji, uruchamiany na procesorze 109 operacji na

sekundę.

Algorytm 2:

sortowanie przez scalanie, zakodowany w C++, wykonuje

60 n lg n operacji, uruchamiany na procesorze 107 op/s.

n=1000, lg 1000 = 10, czas wykonania:

Algorytmy i struktury danych – wykład 1 Strona: 4

A1: 0,003 sekundy

A2: 0,06 sekundy

Wniosek: A1 jest 20 razy szybszy

n=1000000, lg 1000000 = 20,

A1: 3 000 sekund

A2: 120 sekund

Wniosek: A2 jest 25 razy szybszy

Dla większych n porównanie wypada jeszcze korzystniej dla

algorytmu A2.

Wniosek:

należy poszukiwać algorytmów, których liczba

wykonywanych instrukcji jest funkcją o jak najmniejszym

rzędzie szybkości wzrostu.

Zatem przeprowadzamy:

analizę asymptotyczną czasu działania algorytmu

czyli jak zachowuje się funkcja opisująca czas działania

algorytmu gdy rozmiar danych dąży do nieskończoności.

Język zapisu algorytmów na kursie ASD:

uproszczony język programowania w wersji:

• bloki instrukcji będziemy obejmować { }

• semantyka instrukcji: WHILE, FOR, REPEAT, IF_ELSE jak w

Pascalu/C++/Java

• komentarze: //

• wielokrotne podstawienie, np. i j expr

• zmienne są domyślnie lokalne

• tablice jak w C++, indeksowane od 0, A[k] oznacza element

A[n]; A[i..j] – podtablica

• obiekty specyfikowane przez referencję, w notacji

nawiasowej, np. next(p), right_link(q), info(r)

• parametry przekazywane przez referencję

• "and' oraz "or" wykonywane jako "krótki obwód"

Algorytmy i struktury danych – wykład 1 Strona: 5

Typowe zagadnienia analizy algorytmów:

• poprawność algorytmu (częściowa poprawność, określoność

obliczeń, własność stopu)

• ile zasobu wymaga dany algorytm do wykonania dla danych

podanego rozmiaru – czy można go wykonać przy zadanej

ilości zasobów

• który z podanych algorytmów jest najlepszy (ogólnie lub dla szczególnych danych)

• czy istnieje algorytm lepszy od danego

Podstawową miarą jakości (efektywności) algorytmu jest jego

złożoność obliczeniowa:

ilość zasobu komputerowego potrzebna do wykonania

algorytmu, jako funkcja rozmiaru danych wejściowych.

Jest własnością algorytmu niezależną od jego realizacji w

określonym środowisku programistycznym

Zasoby:

• czas (najważniejszy i najciekawszy)

• pamięć.

Jednostki miary złożoności

zależą od przyjętego kryterium:

Kryterium jednostajne:

• pamięciowa: słowo maszyny (dowolnie wielkie)

• czasowa: wykonanie instrukcji elementarnej; w

szczególności instrukcją elementarną jest każda operacja

arytmetyczna niezależnie od wielkości operandów

Kryterium logarytmiczne:

• pamięciowa: 1 bit

• czasowa: czas wykonania instrukcji arytmetycznej na liczbie n-bitowej i m-bitowej wynosi n+m

Algorytmy i struktury danych – wykład 1 Strona: 6

Rozmiar danych:

funkcja związana z dziedziną algorytmu, o wartościach (na

ogół) w zbiorze liczb naturalnych, np.:

• sortowanie: liczba elementów do posortowania

• obliczanie wartości wielomianu: stopień wielomianu

• sprawdzanie czy liczba jest pierwsza: długość zapisu

binarnego liczby

Złożoność pesymistyczna:

ilość zasobu potrzebna w najgorszym przypadku

Złożoność oczekiwana (średnia):

ilość zasobu potrzebna w "typowym" przypadku

K – algorytm

D – dziedzina algorytmu K:

zbiór wszystkich (zestawów) danych wejściowych

Dn – podzbiór dziedziny; dane rozmiaru n

t(d) – liczba instrukcji elementarnych wykonywanych przez

algorytm K gdy na wejściu jest dana (zestaw) d.

Definicja:

Pesymistyczna złożoność czasowa algorytmu K to funkcja

T : N N, określona następująco:

T(n) = sup { t(d) : d ∈ Dn }

Czyli:

ile czasu w najgorszym przypadku zajmuje wykonanie

algorytmu K na danych rozmiaru n.

Przykład: sortowanie przez wstawianie z wartownikiem

(0) znajdź k takie że A[k] dowolny najmniejszy element

(1) zamień (A[1], A[k])

(2) for j 2 to length(A)-1

(3) { tmp A[j]

( ) // wstaw A[j] do posortowanej A[0..j-1]

(4) i j-1

Algorytmy i struktury danych – wykład 1 Strona: 7

(5) while (A[i] > tmp)

(6) {A[i+1] A[i]

(7) i i-1} // tmp >= A[i]

(8) A[i+1] tmp

}

Czas wykonania zależy od danych wejściowych.

Oznaczmy:

n := length(A)

tj := liczba iteracji linii 5 dla ustalonego j

(0) koszt: (n-1), liczba wykonań:

1

(1)

1,

1

(2)

1,

n-1

(3)

1,

n-2

(4)

1,

n-2

(5)

1,

,

(6)

1,

(t2-1)+ . . . + (tn-1-1),

(7)

1,

(t2-1)+ . . . + (tn-1-1),

(8)

1,

n-2

Kładziemy: rozmiar danych = length(A) = n

Czas (n)=(n-1)+ 1 + (n-1) + (n-2) + (n-2) + (t2 + . . . + tn-1)+ ((t2-1)+ . . . + (tn-1-1)) + ((t2-1)+ . . . + (tn-1-1))+ n -2

Przypadek najlepszy (tablica uporządkowana):

tj = 1, dla j=2,...,n-1

wówczas

Czas (n)=(n-1)+ 1 + (n-1) + (n-2) + (n-2) + (t2 + . . . + tn-1)+ n -2 = 5n -7 + n -2 = 6n -9

Przypadek pesymistyczny(tablica odwrotnie uporządkowana):

tj = j, j=2,...,n-1

wówczas

Czas(n) = 5n – 7 + (2+...+n-1) + 2*(1+...+(n-2))

= 6n – 9 + 3*(1+ ... + n-2)

Algorytmy i struktury danych – wykład 1 Strona: 8

= 6n – 9 + (n-1)(n-2)/2

= 1.5n2 + 1.5n – 4.5

Zatem, złożoność czasowa (pesymistyczna):

T(n) = 1.5n2 +1.5n – 4.5

Dalsze oznaczenia:

Xn – zmienna losowa, której wartościami są t(d)

funkcja przypisująca zdarzeniu, polegającemu na

wylosowaniu danej rozmiaru n, liczby wykonanych przez

algorytm K instrukcji elementarnych na danej d

pnk – rozkład zmiennej Xn

prawdopodobieństwo, że dla losowej danej rozmiaru n

algorytm K wykona k instrukcji

Definicja: Średnia złożoność czasowa algorytmu K to

funkcja:

A(n) = Σk≥0 k * pnk

Czyli:

jest to wartość oczekiwana zmiennej losowej Xn

inne oznaczenia: E(Xn), ave(Xn).

Złożoność średnia sortowania przez wstawianie z

wartownikiem:

A(n) = 0.25 n2 + cn + d, dla pewnych stałych c, d

Wrażliwość algorytmu:

na ile T(n), A(n) są reprezentatywne dla wszystkich danych

Miara pesymistycznej wrażliwości:

∆(n) = sup {t(d1) – t(d2) : d1, d2 ∈ Dn) }

Miara oczekiwanej wrażliwości:

δ(n) = dev(Xn)

odchylenie standardowe zmiennej losowej

gdzie:

dev(Xn) = √ var(Xn),

var(Xn) = Σk≥0 (k – E(Xn))2 pnk

Algorytmy i struktury danych – wykład 1 Strona: 9

Notacja “O duże”:

Na ogół wystarcza oszacowanie z dokładnością do

współczynnika – istotny tylko rząd wielkości funkcji

złożoności

O(f(n)) = rodzina wszystkich funkcji, których rząd prędkości

wzrostu nie przekracza rzędu funkcji f(n).

Formalnie:

f, g : N R+

f (n) ∈ O(g(n))

(”f jest co najwyżej rzędu g", "f jest O duże od g”) jeśli istnieje stała rzeczywista c oraz naturalna n0 taka, że f(n) ≤ c g(n), dla wszystkich n≥ n0.

Powszechnie przyjęte oznaczenie:

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

Wniosek:

Złożoność algorytmu sortowania przez wstawianie z

wartownikiem: O(n2).

Przykładowe własności notacji "O":

• f(n) = O(g(n)), g(n) = O(h(n))

f(n) = O(h(n))

(przechodniość)

• f(n) = O(h(n)), g(n) = O(h(n))

f(n) + g(n) = O(h(n))

• f(n) <= g(n), dla każdego n

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

• f(n) = c*g(n), dla każdego n, gdzie c jest stałą

Algorytmy i struktury danych – wykład 1 Strona: 10

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

• f(n) + g(n) = O(max(f(n), g(n)))

W szczególności zatem:

• wielomian W(x) jest stopnia k W(n) = O(nk)

• jeśli liczba operacji nie zależy od rozmiaru danych

wejściowych

złożoność algorytmu jest stała: O(1)

Aby uściślić szacowanie rzędu wielkości (wzrostu funkcji):

Notacja "omega duże" – odwrotna nierówność

(rzędu co najmniej ...)

f(n) = Ω (g(n)), jeśli g(n) = O(f(n))

Notacja "theta duże" – rzędu dokładnie ...

f(n) = Θ (g(n))

jeśli f(n) = O(g(n)) oraz f(n) = Ω (g(n)).

Przykłady:

• Jeśli wielomian W(x) jest stopnia k, to zachodzi

W(n) = Θ (nk)

Dodatkowa metoda unikania szczegółów technicznych realizacji

algorytmu:

Instrukcje dominujące w algorytmie

to takie instrukcje, że liczba wszystkich wykonywanych

instrukcji elementarnych jest proporcjonalna do liczby wykonań instrukcji dominujących.

Np.

Algorytmy i struktury danych – wykład 1 Strona: 11

• porównanie elementów w algorytmie sortowania (nie każdym

– w algorytmie sortowania przez wstawianie: tak)

• operacja modulo w algorytmie Euklidesa (kryterium

jednostajne)

Typowe funkcje złożoności:

1. log n

oznacza log2n

np. wyszukiwanie połówkowe

2. n

liniowa,

np. wyszukiwanie w liście

3. n log n

liniowo logarytmiczna

np. sortowanie przez scalanie

4. n2

kwadratowa,

np. sortowanie przez wstawianie

5. n3, n4, itd. dalsze złożoności wielomianowe

- - - - - - - - - - - -

6. 2n

wykładnicza,

np. przegląd wszystkich podzbiorów

7. n!

silnia

np. przegląd wszystkich permutacji.

Dwukrotny wzrost rozmiaru zadania powoduje zwiększenie

czasu:

Ad. 1.

tylko o 1 jednostkę

Ad. 5.

8-krotne, 16-krotne itd.

Ad. 6.

poprzedni czas do kwadratu

Złożoność wykładnicza praktycznie uniemożliwia wykonanie

algorytmu dla nawet umiarkowanego rozmiaru danych (nie-

realizowalność algorytmu)

T(n) = 2n

Algorytmy i struktury danych – wykład 1 Strona: 12

n=

20

50

100

200

106 op/s

1.04s 35.7 lat 4*1016 lat 5*1046 lat

109 op/s 0.001s 13 dni

4*1013 lat 5*1043 lat

“Tyrania rzędu szybkości wzrostu”

dla złożoności wykładniczej:

Zakładając ten sam czas wykonania (np. 1 dzień):

Wzrost szybkości komputera 1000 razy

pozwala zwiększyć rozmiar zadania TYLKO o około 10

Wniosek:

Istnienie algorytmu o złożoności wielomianowej dla

danego problemu jest kwestią kluczową.

Reguły szacowania złożoności z użyciem "O

duże":

Pętla 'for': Złożoność pętli 'for' jest równa złożoności instrukcji wewnątrz pętli (włącznie z operacjami nagłówka pętli)

pomnożonej przez liczbę iteracji.

sum 0

for i1 to n

{ sum sum + i*i*i }

Złożoność: 6n + 2 = Θ(n)

Zagnieżdżone pętle 'for': Całkowity koszt czasowy instrukcji wewnątrz zagnieżdżonych pętli 'for' jest równy złożoności tych instrukcji pomnożonej przez iloczyn rozmiarów tych pętli.

Algorytmy i struktury danych – wykład 1 Strona: 13

for i1 to n

{

for j1 to n { k++ }

}

Złożoność: Θ(n2)

Koszt ciągu instrukcji: jest równy sumie kosztów wszystkich instrukcji i jest rzędu dokładnie największego z kosztów tych instrukcji (czyli: dla notacji "o duże" liczy się tylko największy z kosztów).

Uwaga:

zakładamy że długość ciągu instrukcji jest stała, niezależna od rozmiaru danych.

sum 0

for i1 to n

{

sum sum + i*i*i }

for i1 to n

{

for j1 to n { k++ }

}

Złożoność: Θ(1) + Θ(n) + Θ(n2) = Θ(n2)

Przykład innej typowej funkcji złożoności:

for i1 to n

{ j1

while (j<=n)

{ k++

j2*j

}

}

Złożoność: Θ (n lg n)

Analiza złożoności a praktyczne uwarunkowania

Algorytmy i struktury danych – wykład 1 Strona: 14

Sytuacje, które mogą ograniczyć stosowalność analizy

złożoności

• algorytm wyrażony w innym języku niż jego realizacja

• z powodu wrażliwości zachowanie algorytmu na typowych

danych różne od T(n) i A(n)

• niemożność ustalenia rzeczywistego rozkładu Xn

• trudność matematycznego oszacowania T(n), a zwłaszcza

A(n)

• trudność jednoznacznego porównania dwóch algorytmów –

każdy z nich lepszy w różnych okolicznościach i dla różnych

danych

Bardzo ważna cecha algorytmu: prostota jest decydującym kryterium wyboru algorytmu gdy program:

• wykonywany niewielką liczbę razy, lub

• stosowany tylko dla małych danych