Notacja O.

Załóżmy, ze mamy dwie funkcje f (n) i g(n). Mówimy, ze funkcja f (n) jest O(g(n)) („O duże od g od n”) jeżeli istnieje stała dodatnia c, taka ze dla prawie wszystkich n

0 <=f (n) <= c · g(n).

Piszemy f (n) = O(g(n)).

Przykłady:

2n + 7 = O(n),

n3 + 2n2 − n + 4 = O(n3),

n = O(n2),

| sin(n)| = O(1),

nk = O(2n) dla dowolnego k.

Notacja Ω.

Podobnie jak notacja O określa asymptotyczne ograniczenie górne, notacja Ω określa asymptotyczne ograniczenie dolne.

Załózmy, ze mamy dwie funkcje f (n) i g(n). Mówimy, ze funkcja

f (n) jest Ω(g(n)) („Omega duże od g(n)”) jeżeli istnieje stała dodatnia c, taka ze dla prawie wszystkich n

f (n) >= c · g(n) >= 0.

Piszemy f (n) = Ω (g(n)).

Przykłady:

2n − 7 = Ω (n),

n3 − 2n2 + n + 4 = Ω (n3),

nk = (log n), dla dowolnego k > 0.

Notacja Θ.

Mówimy, ze funkcja f (n) jest Θ(g(n)) („Theta duze od g(n)”) jeżeli istnieją dodatnie stałe c1, c2, takie ze dla prawie wszystkich n c1g(n) >= f (n) >= c2g(n) >= 0. Piszemy f (n) = Θ (g(n)). Mówimy, ze g(n) jest asymptotycznie dokładnym oszacowaniem dla f(n).

Przykłady:

2n − 7 = Θ(n),

n3 − 2n2 + n + 4 = Θ(n3).

Dla dowolnych funkcji f (n) i g(n) zachodzi zależność

f (n) = Θ(g(n)) wtedy i tylko wtedy gdy f (n) = O(g(n)) i

f (n) = (g(n)).

Kopiec (heap) binarny jest to drzewo binarne w którego węzłach znajdują się pewne wartości i które mają własności: - każdy kolejny poziom kopca i zawiera 2ⁱ wierzchołków, z wyjątkiem poziomu ostatniego n, który może mieć od 1 do 2ⁿ wierzchołków. - wartość każdego syna danego węzła jest nie większa niż wartość tego węzła.

Pesymistyczny dolny czas Heapify (kopcowania) jest O(h) gdzie h - wysokość, na której jest element. T(h) -czas pesymistyczny tzn. gdy kopcujemy do samego dołu: T(h)=c₁*h=O(h)

Czas działania build-heap jest O(n) gdzie n - ilośc elementów w kopcu

Pesymistyczny górny czas kopcowania jest O(nlgn) gdzie n - ilośc sortowanych elementów.

Dowód:

T(n)<=O(n)+(n-1)(c1+O(lgn))<=c2*n+(n-1)(c1+c2*lgn)<=c2*n+c1*n+c3*nlgn<=c*nlgn = O(nlgn)

Kolejka priorytetowa jest to struktura danych w której można przechowywać zbior elementów posiadających pewne priorytety i na której są określone operacje: Maximum - daje El. O najwyższym priorytecie, Extract-Max - usuwa z kolejki element o najwyższym priorytecie, Insert(x) - wstawia do kolejki element x o zadanym priorytecie.

Kolejkę priorytetową implementujemy jako kopiec uporządkowany

Złożoność operacji: Maximum - Θ(1), Extract-Max i Insert - Θ(lgn)

Uzasadnienie: algorytmy wędrują w najgorszym wypadku przez cały kopiec (lgn); na każdym poziomie jest stała ilość operacji.

Czas:	optymistyczny	Typowy	pesymistyczny
Boubble sort	O(n^2)	O(n^2)	O(n^2)
Merge sort	O(n log n)	O(n log n)	O(n log n)
Heap sort	O(n log n)	O(n log n)	O(n log n)
Quick sort	O(n log n)	O(n log n)	O(n^2)

QuickSort: Pesymistyczny czas górny jest Θ(n²) Dowód: T(n) <=n*c₁*n=c₁*n²=Θ(n²)

Pesymistyczny czas dolny T(n)>=c1[(n+2)(n+1)]/2>=c1*n/2 tzn. Ω(n²)

Oczekiwana złożoność obliczeniowa algorytmu z losowym wyborem elementu wyznaczającego podział jest Θ(nlgn)

Złożoność algorytmu randomized-select to Θ(n²) dla dowolnego przypadku gdyż może zajść sytuacja że zawsze będziemy wybierać największy pozostały element jako punkt podziału.

Algorytmy sortowania w czasie liniowym:

Czas:	Optymistyczny	typowy	pesymistyczny
Bucket sort	O(m + n)	O(m + n)	O(m + n)
Counting sort	O(m + n)	O(m + n)	O(m + n)
Radix sort	O(n log n)	O(n log n)	O(n log n)

Algorytmy te mają inną złożonośc obliczeniową niż algorytmy porównujące gdyż do sortowania nie wykorzystują tylko porównań. Ograniczenia użycia tych algorytmów: Dla wielkich liczb

elementarne struktury danych:

Czas:	Insert	Delete	Serach
Stos	O(1)	O(1)	-
Kolejka	O(1)	O(1)	-
Lista	O(1)	O(1)	Θ(n)

Tablice z haszowaniem i łańcuchową metodą rozwiązywania konfliktów

Wstawianie i usuwanie O(1).

Średni czas z metodą łańcuchową Θ(1+m) m - współczynnik zapełnienia

Pesymistyczny czas z metodą łańcuchową Θ(1+m)

Złożoność oczekiwana metodą łańcuchową zakończona porażką Θ(1+m). Ponieważ jest on równy przejściu jednej z list. Średnia długość listy jest równa współczynnikowi zapełnienia.

haszowanie z adresowaniem otwartym:

Postać funkcji haszującej w metodzie liniowej: h(k,i)=(h'(k)+i)mod m, 0<=i<=m

Postać funkcji haszującej w metodzie kwadratowej: h(k,i)=(h'(k)+c₁i+c₂i²)mod m, 0<=i<=m

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).

Drzewa poszukiwań binarnych:

Są to struktury danych, na których można wykonywać operacje charakterystyczne dla zbiorów dynamicznych takie jak serach, maximum, minimum, predecesor, successor, insert oraz delete.

Pesymistyczny czas dowolnej z tych funkcji to O(h) gdzie h oznacza wysokość drzewa. Wynika to z faktu że program nie może „chodzić” nigdzie dalej niż na maksimum wysokości drzewa.

Losowo skonstruowane drzewo poszukiwań binarnych:

Jest to drzewo zbudowane przez serię (n) wywołań funkcji insert z losowymi wartościami. Wysokość oczekiwana takiego drzewa to O(lgn)

Wniosek o oczekiwanej złożoności wstawiania: do pustego drzewa wstawiamy n losowych różnych kluczy k₁,k₂…k_n ,dla danego klucza kj określamy:

G_j={k_i:l<=i<=j i k_l>k_i>k_j dla każdego l<i takiego że k_l>k_j}

L_j={k_i:l<=i<=j i k_l<k_i<k_j dla każdego l<i takiego że k_l<k_j}

Wtedy na ścieżce od korzenia do klucza k_j znajdują się tylko klucze z G_j∪L_j a głębokość klucza k_j w drzewie wynosi |G_j|+|L_j|

Drzewa czerwono-czarne:

Jest to drzewo przeszukiwań binarnych z dodatkowa informacją oznaczająca jego kolor (RED/BLACK) z narzuceniem odpowiednich warunków, gwarantujące że kazda ścieżka jest maksymalnie 2x dłuższa niż każda inna. Własności:

-Każdy węzeł jest czerwony lub czarny.

-Korzeń jest czarny.

-Każdy liść jest czarny (Można traktować nil jako liść).

-Jeśli węzeł jest czerwony, to jego synowie muszą być czarni.

-Każda ścieżka z ustalonego węzła do liścia liczy tyle samo czarnych węzłów.

Drzewo RB o n węzłach ma wysokość co najwyżej 2lg(n+1)

W operacjach wstawiania i usuwania może zostać zakłócona własność „Jeśli węzeł jest czerwony, to jego synowie muszą być czarni”, którą przywracamy za pomocą rotacji i ponownego kolorowania węzłów. Zakłócenie to wynika z pojawienia się nowego elementu lub usunięciu innego które podtrzymywały własność.

Czasy: Wstawianie - O(lgn), Usuwanie - O(lgn)

B-drzewa:

Definicja: B-drzewo jest to drzewo przeszukiwań binarnych posiadające węzły o następujących właściwościach: (węzeł x)

x[n] - n ilość elementów w węźle przy czym x[1]<x[2]<[x3] itd.

x[Leaf] - oznacza czy węzeł jest liściem

jeśli nie jest liściem ma n+1 wskaźników na następne węzły.

Klucze węzła x definiują przedziały wartości poddrzew węzła x

Wszystkie liście są na tej samej głębokości.

Każde b-drzewo ma swój minimalny stopień t >=2, który określa minimalną i maksymalna ilość elementów w węźle

Drzewa dwumianowe:

Drzewo dwumianowe to takie które składa się z dwóch innych drzew dwumianowych z uporządkowanego ciągu (odpowiednio drzewo D_k składa się z drzew D_k-1 i D_k-2 Które są synami root'a drzewa D_k)

Własności:

W drzewie D_k jest 2^k węzłów

Wysokość drzewa wynosi k

(^k_i) węzłów znajduje się na wysokości i drzewa

Stopień drzewa wynosi k i jest większy od stopnia każdego innego węzła.

Maksymalny stopień węzła w n-węzłowym drzewie wynosi logn

Kopce dwumianowe:

Definicja: zbiór drzew dwumianowych, które pamiętają elementy z uporządkowanego uniwersum w porządku kopcowym.

Operacje na kopcach:

Znajdowanie minimalnego klucza - O(lgn)

Łączenie dwóch kopców - O(lgm) m-liczba korzeni

Wstawianie węzła - O(1) [tworzenie] + O(lgn) [wstawianei do n elementowego kopca]

Usuwanie - O(lgn)

Zbiory rozłączne:

Jest to grupowanie n różnych zbiorów w grupę zbiorów rozłącznych, wykonujemy na nich dwie operacje: wyszukanie zbioru do którego należy element oraz łączenie dwóch zbiorów.

Przykładowe zastosowanie zbiorów rozłącznych to algorytm Kruskala, który zapisuje różne kombinacje grafu przejść jako zbiory rozłączne.

Listowa reprezentacja zbiorów rozłącznych:

Operacje:

Ciąg m operacji typu Find oraz Union ma czas O(m + nlgn) gdzie n to ilośc operacji Make-Set potrzebnych do wykonania operacji Find lub Union

---