1.

Koszt pesymistyczny operacji (insert) wstawiania i usuwania (delete) do B - drzewa jest rzędu wysokości drzewa O(h)=O(logt n).

Złożoność pesymistyczna (Search): T (n  n  (n max - przypadek drzewa zdegenerowanego.

Złożoność średnia: O(logn) - określony na postawie wyników eksperymentów, ale nieudowodniony.

2.

Kopiec binarny jest binarnym drzewem zupełnym, w którego węzłach są pamiętane elementy w porządku kopcowym. W drzewie binarnym jest zachowany porządek kopcowy, gdy element w każdym węźle wewnętrznym jest nie mniejszy od kluczy w jego synach i dalszych potomkach.

Wysokość:

h log t (n1)/2

3.

Built-Heap - Dzięki logarytmicznej złożoności pojedynczych operacji wstawiania (rozszerzania kopca), całkowita złożoność tego etapu to O(nlog n).

Sort-Heap - Polega na usunięciu wierzchołka kopca, zawierającego element maksymalny, a następnie wstawieniu w jego miejsce elementu z końca kopca i odtworzenie porządku kopcowego. W zwolnione w ten sposób miejsce, zaraz za końcem zmniejszonego kopca wstawia się usunięty element maksymalny. Operacje te powtarza się aż do wyczerpania elementów w kopcu. Złożoność tej fazy to także O(nlog n)

4. ????

5.

Quicksort

W przypadku pesymistycznym, jeśli zawsze wybierzemy element najmniejszy (albo największy) w sortowanym fragmencie tablicy, to:

skąd wynika kwadratowa złożoność czasowa:

6.

Algorytmy sortujące za pomocą porównań- to takie algorytmy sortowania, których sposób wyznaczania porządku jest oparty wyłącznie na wynikach porównań między elementami; Dla takich algorytmów dolne ograniczenie złożoności wynosi Ω(n log n)

7.

Przeszukiwanie liniowe- to najprostszy algorytm wyszukiwania informacji w ciągu danych, np. zapisanych w tablicy lub na liście. Polega na porównywaniu żądanego klucza z kolejnymi kluczami z sekwencji danych - wyszukiwanie kończy się powodzeniem, gdy zostanie znaleziony klucz, albo niepowodzeniem, gdy zostaną przejrzane wszystkie klucze.

Liczba koniecznych porównań zależy wprost od położenia szukanego elementu w sekwencji danych - wynosi od 1 do n, gdzie n to całkowita liczba elementów. Algorytm ma złożoność O(n).

Ograniczenia: dla dużej liczby danych algorytm jest bardzo nieefektywny jednak, gdy danych jest względnie mało, może być z powodzeniem stosowany.

8.

Stos (ang. Stack) - liniowa struktura danych, w której dane dokładane są na wierzch stosu i z wierzchołka stosu są pobierane. Złożoność pesymistyczna operacji na stosach jest stała Ө (1) dla implementacji tablicowych i dowiązaniowych. Wstawianie (Push), Zdejmowanie(Pop), Sprawdzanie czy jest pusty (Empty-Stack).

Push:

Implementacja Tablicowa:

S:

1 2 . . . Top[S]- pozycja wierzchołka stosu

Push(S,x)- wstawienie elementu S na stos x.

Top[S]= Top[S]+1

S[Top[S]] ← x

Pop:

Pop(S)

If Empty-stack (S) then błąd

Else

Top[S] ← Top[S]-1

Return S[Top[S]+1]

Empty-stack:

Empty-stack(S)

If Top[S]=0

Then return TRUE

Else return FALSE

Kolejka (ang. queue) - liniowa struktura danych, w której nowe dane dopisywane są na końcu kolejki, a z początku kolejki pobierane są dane do dalszego przetwarzania FIFO (first in first out). Złożoność pesymistyczna operacji na kolejkach jest stała Ө (1) dla implementacji tablicowych i dowiązaniowych. Wstawianie (enqueue), Zdejmowanie( dequeue),

Q

Length(Q)

Pierwsza wolna pozycja tail (Q)

Pierwszy w kolejce head(Q)

Enqueue (Q,x)

If full-Queue (Q) then błąd

Else

Q[Tail[Q]] ← x

If Tail [Q] = length [Q]

Then Tail[Q] ← 1

Else Tail[Q] ← Tail[Q]+1

Dequeue (Q,x)

If empty-Queue (Q) then błąd

Else

x ← Q[head[Q]]

If head [Q] = length [Q]

Then head[Q] ← 1

Else head[Q] ← head[Q]+1

Return x

empty-Queue [Q]

If head [Q] = Tail[Q]

Then return True

Else return False

full-Queue [Q]

If Tail [Q] = length [Q] oraz head[Q]+1

Then return True

If head[Q] = Tail[Q]+1

Then return True

Else return False

Listy ??

9.

Funkcje haszujące

Dobra funkcja haszujaca powinna spełniać: założenie prostego równomiernego haszowania: losowo wybrany klucz jest z jednakowym prawdopodobieństwem odwzorowywany na każdą z m pozycji w tablicy, niezależnie od tego, gdzie zostają odwzorowane inne klucze.

Przykład:

Załóżmy, że klucze są losowymi liczbami rzeczywistymi rozłożonymi niezależnie i równomiernie w przedziale [0, 1). Wtedy funkcja h: U ! {0, . . .m − 1} dana wzorem h(k) = [mk] spełnia warunek prostego równomiernego haszowania.

Rozwiązywanie kolizji metodą łańcuchową

Wszystkie elementy, którym odpowiada ta sama wartość w tablicy, zostają umieszczone na jednej liście. Tablica haszującą jest w tym przypadku tablica wskaźników na listy tych elementów, które maja taka sama wartość funkcji haszującej.

Złożoność pesymistyczna operacji na tablicy haszowej z łańcuchową metodą rozwiązywania konfliktów jest następująca:

Wstaw: Ө(1) - czas stały

Szukaj: Ө(n) - n- ilość Ele. W tablicy

Usuń: Ө(1) przy rozsądnej implementacji

Oczekiwany czas szukania zakończono porażką w tablicy haszowań z łańcuchową metodą rozwiązywania konfliktów, przy założeniu równomiernego haszowania jest:

m- rozmiar tablicy

α - współczynnik wypełnienia

n- ilość elementów w tablicy

0(1+ α) , gdzie α= n/m

uzasadnienie:

m- list, n- elementów równomiernie rozłożonych, średnia dł. Listy n/m

czas wstawiania 0(1+α)

wniosek: Jeżeli n=0(m) np. n<m to α=0(1)(jest stałe).

10.

Adresowanie otwarte- wszystkie elementy słownika są przechowywane wprost w tablicy. Wyszukiwanie elementu polega na systematycznym sprawdzaniu pozycji w tablicy, aż zostanie znaleziony szukany element albo wiadomo już, że na pewno nie ma go w tablicy. Nie ma żadnych dodatkowych list. Przy stosowaniu haszowania otwartego współczynnik zapełnienia  nie może większy od jedynki, aby nie nastąpiło przepełnienie

tablicy.

Liniowa: h(e, i  (h' (e imod m

Gdzie h - pomocnicza jednoargumentowa funkcja haszująca

Dwukrotna: h(e, i (h1 (e ih2 (emod m

Gdzie h - pomocnicza jednoargumentowa funkcja haszująca,

Kwadratowa: h(e, i (h' (e c1 i+ c2 i² mod m

Gdzie h - pomocnicza jednoargumentowa funkcja haszująca, c1 i c2 =/ 0 są stałymi, i= 0,1,…,m-1.

Złożoność haszowania otwartego: Jeżeli współczynnik zapełnienia tablicy z haszowaniem a= n/ m<1, to średnia liczba porównań wykonanych w czasie realizacji operacji search i insert metodą adresowania otwartego jest nie większą niż 1/1- a, o ile jest spełnione

założenie o równomiernym haszowaniu.

. . .

---