Algorytmy i Struktury Danych
dr Karol Grudziński
Uniwersytet Kazimierza Wielkiego
i
Wyższa Szkoła Gospodarki

Pojęcia Podstawowe
"
Komputery stały się narzędziem powszechnego
użytku a ich zastosowania daleko wykraczają
poza pierwotny jedyny cel: obliczenia.
"
Takie a nie inne możliwości ich zastosowania
wynikają z odpowiedniego ich zaprogramowania.
"
Algorytmy i Struktury Danych to dziedzina o
silnych podstawach teoretycznych, wywodząca
się z matematyki i informatyki.
"
Znajomość fundamentów tej dziedziny jest
niezbędna do sprawnego i wydajnego
programowania. 2

ALGORYTM: Formalny przepis wykonania
określonej czynności. Ciąg instrukcji służących
wykonaniu jakiegoś zadania.

Do zaprogramowania konkretnego zadania
możemy na ogół użyć jednego z wielu algorytmów
 wybór jakiegoś konkretnego decyduje jak
szybko komputer wykona zadanie i ile zasobów
będzie potrzebne.

Efektywność rozwiązania danego problemu przy
użyciu danego algorytmu  czy to pod względem
szybkości czy zasobów - jest często nie tylko
cechą samego algorytmu ale i zależy od
konkretnych danych. 3

TEORIA ZA
OŻONOŚCI: umożliwia określenie
żarłoczności algorytmu w odniesieniu do różnych
zasobów, z których najważniejszy jest zazwyczaj
czas realizacji i zajętość pamięci.

Dla większości rozwiązywanych problemów
wybór konkretnego algorytmu to sprawa
kompromisu między czasem realizacji a
zajętością pamięci: szybsze algorytmy na ogół
wymagają większych pamięci. 4
Notacja 'dużego O'

Podstawową miarą efektywności algorytmu jest
zależność czynnika stanowiącego o tej
efektywności (najczęściej czasu wykonania) od
rozmiaru problemu.

Przykład sortowania: mamy dwa algorytmy
sortowania, 1: sortuje tysiąc liczb w 1s a milion w
10s; 2: tysiąc w 2s a milion w 5s.

Wniosek: wartości bezwzględne czasów
wykonania nie na wiele się zdają przy
porównywaniu obydwu algorytmów  wyższość
któregoś z nich uwarunkowana jest rozmiarem
danych. 5

Teoria złożoności interesuje się głównie zależnością
efektywności algorytmu od rozmiaru problemu, gdy
ten ostatni wzrasta nieograniczenie.

Zatem nie jest istotna dokładna formuła zależności
efektywności od rozmiaru problemu lecz jej
zachowanie asymptotyczne (np. W przypadku
zależności wielomianowych wpływ ma wyraz w
najwyższej potędze).

Podobnie, drugorzędne znaczenie posiadają stałe
współczynniki: jeżeli program korzystający z
algorytmu o złożoności 5N^2 uruchomić na
dwukrotnie szybszym komputerze zaobserwujemy
złożoność 2.5N^2. Stały czynnik ma charakter
względny  stała pozostaje zależność kwadratowa. 6

Notacja dużego O: aby przy analizie zachowań
asymptotycznych nie zagłębiać się w mniej istotne
szczegóły  którymi są wyrazy w niższych potęgach
oraz stałe współczynniki  wprowadzono w
matematyce notację odzwierciedlającą wzajemny
związek pomiędzy asymptotycznym zachowaniem się
dwu funkcji.

Def: Mówimy, że funkcja f jest rzędu funkcji g, co
zapisujemy f = O(g), jeżeli funkcje te w
nieskończoności zbliżają się do siebie z dokładnością
do stałego czynnika, tj. Istnieje taka stała dodatnia C,
że
lim sup |f(x)| / |g(x)| = C
x" 7
Cechy struktur danych: Tablica
Zalety Wady
szybkie wstawianie, szybki wolne
dostęp, o ile znany indeks wyszukiwanie,
wolne
usuwanie,
stały rozmiar
Wyszukiwanie Wstawianie Usuwanie Obchód
O(N) O(1) O(N) --
8
Tablica uporządkowana
Zalety Wady
szybsze wyszukiwanie niż wolne wstawianie i
w tablicy nieuporządkowanej usuwanie, stały
rozmiar
Wyszukiwanie Wstawianie Usuwanie Obchód
O(log N) O(N) O(N) O(N)
9
Stos
Zalety Wady
dostęp typu  ostatni na wejściu, wolny dostęp do
pierwszy na wyjściu (LIFO) innych elementów
Wstawianie Usuwanie Komentarz
O(1) O(1) Usuwa ostatnio wstawiony
element
10
Kolejka
Zalety Wady
dostęp typu  pierwszy na wejściu - wolny dostęp do
pierwszy na wyjściu (FIFO) innych elementów
Wstawianie Usuwanie Komentarz
(implementacja za pomocą tablicy lub listy powiązanej):
O(1) O(1) Usuwa najdawniej wstawiony
element
(kolejka priorytetowa implementowana tablicą uporządkow.):
O(N) O(1) Usuwa element o najwyższym
priorytecie
(kolejka priorytetowa implementowana stertą):
Usuwa element o najwyższym
O(log N) O(log N) priorytecie 11
Lista powiązana
Zalety Wady
szybkie wstawianie i usuwanie Wolne wyszukiwanie
Wyszukiwanie Wstawianie Usuwanie Obchód
O(N) O(1) O(N) --
Uporządkowana lista powiązana:
O(N) O(N) O(N) O(N)
12
Drzewo binarne
Zalety Wady
Szybkie wyszukiwanie, wstawianie i Skomplikowany
usuwanie (o ile drzewo jest algorytm
zrównoważone) usuwania
Wyszukiwanie Wstawianie Usuwanie Obchód
Średni Przypadek:
O(log N) O(log N) O(log N) O(N)
Najgorszy Przypadek:
O(N) O(N) O(N) O(N)
13
Drzewo czerwono-czarne
Zalety Wady
Szybkie wyszukiwanie, wstawianie i Skomplikowane
usuwanie. Drzewo zawsze
zrównoważone.
Wyszukiwanie Wstawianie Usuwanie Obchód
O(log N) O(log N) O(log N) O(N)
14
Drzewo 2-3-4
Zalety Wady
Szybkie wyszukiwanie, wstawianie Skomplikowane
i usuwanie. Drzewo zawsze
zrównoważone. Nadaje się do
przechowywania danych w pamięci
dyskowej.
Wyszukiwanie Wstawianie Usuwanie Obchód
O(log N) O(log N) O(log N) O(N)
15
Tablica przemieszczania
Zalety Wady
Bardzo szybki dostęp o ile znany Wolne usuwanie,
jest klucz. Szybkie wstawianie. Wolny dostęp,
jeśli nie jest znany
klucz, nieefektywne
wykorzystanie
pamięci
Wyszukiwanie Wstawianie Usuwanie Obchód
O(1) O(1) O(1) --
16
Sterta
Zalety Wady
Szybkie wstawianie, usuwanie, Wolny dostęp do
dostęp do największego elementu innych elementów
17
Złożoność niektórych algorytmów
dla tablic

Wyszukiwanie liniowe: O(N)

Wyszukiwanie binarne: O(log N)

Wstawianie do nieuporządk. tablicy: O(1)

Wstawianie do uporządk. tablicy: O(N)

Usuwanie z nieuporządk. tablicy: O(N)

Usuwanie z uporządk. tablicy: O(N)

Sortowanie bąbelkowe: O(N^2)

Sortowanie przez wstawianie, dane losowo: O(N^2)

Sortowanie przez wstawianie, część. posortow..: O(N^2)

Sortowanie kolumnowe: O(N^3/2)

Sortowanie szybkie (najgorszy czas): O(N^2)

Sortowanie szybkie (średni czas): O(N * log N)

Sortowanie przez łączenie: O(N * log N)

Sortowanie stertowe: O(N * log N)
18
Algorytm wyboru struktury danych
19