Θ (g(n)) - wielkie theta od g od n … 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) … dokł. oszacowanie
O (g(n)) - wielkie o od g od n … 0 ≤ f(n) ≤ cg(n) … organicznie górne
o (g(n)) - małe o od g od n … 0 ≤ f(n) < cg(n) … organicznie górne
Ω (g(n)) - wielkie omega od g on n … 0 ≤ cg(n) ≤ f(n) … ograniczenie dolne
ω (g(n)) - małe omega od g od n … 0 ≤ cg(n) < f(n) … ograniczenie dolne
INSERTION-SORT (INSERT-SORT)
Sortowanie przez wstawianie.
- wydajne dla danych wstępnie posortowanych
- wydajne dla zbiorów o niewielkiej liczebności
- stabilne
- działa w miejscu
Θ(n2) Insertion-Sort
Θ(n) Insertion-Sort (dla posortowanych danych)
MERGE-SORT
Sortowanie przez scalanie.
-stabilne
Θ(nlg(n)) Merge-Sort
Θ(n) Merge (wykonuje scalanie tablic)
HEAP-SORT
Sortowanie przez kopcowanie.
-skuteczne dla złośliwych danych
-łatwy do zrównoleglenia
-działa w miejscu
-wysokość kopca wynosi O(lg(n))
O(nlg(n)) Heap-Sort
O(lg(n)) Max-Heapify / Heapify (przywraca własności kopca)
O(lg(n)) Heap-Extract-Max (usuwa i zwraca element o największym kluczu)
O(lg(n)) Max-Heap-Insert / Heap-Insert (generalnie dodawanie elementów do kopca)
O(lg(n)) Heap-Increase-Key (zmienia wartość danego klucza na większą lub równą)
O(lg(n) Heap-Maximum (zwraca element o największym kluczu)
O(n) Build-Max-Heap / Build-Heap (tworzy kopiec z tablicy danych wejściowych)
QUICK-SORT
Sortowanie szybkie.
-wysoka średnia skuteczność Θ(nlg(n))
-żadne określone dane wejściowe nie
prowadzą do przypadku pesymistycznego (algorytm probalistyczny)
-działa w miejscu
Θ(n2) Qucik-Sort
Θ(n lg(n)) Randomized-Qucik-Sort
O(n lg(n) Randomized-Partition (dzieli tablicę względem wylosowanego elementu)
O(n) Partition (dzieli tablicę)
COUNTING-SORT
Sortowanie przez zliczanie.
-stabilne
-wysoka średnia skuteczność:
O(n+k) Counting-Sort
BUCKET-SORT
Sortowanie kubełkowe.
-stabilne
-wysoka średnia skuteczność:
Θ(n) Bucket-Sort
RADIX-SORT
Sortowanie pozycyjne.
-stabilne
-wysoka średnia skuteczność:
Θ(d(n+k)) Radix-Sort
RANDOMIZED-SELECT
Rekurencyjny podział tablicy.
-wysoka średnia skuteczność Θ(n)
-żadne określone dane wejściowe nie
prowadzą do przypadku pesymistycznego (algorytm probalistyczny)
Θ(n2) Randomized-Select
O(n lg(n) Randomized-Partition (dzieli tablicę względem wylosowanego elementu)
O(n) Partition (dzieli tablicę)
O(n) Select (zwraca i-ty najmniejszy element zbioru)
TABLICE HASZUJĄCE
-szybkie wyszukiwanie element o danym kluczu
DRZEWA WYSZUKIWAŃ BINARNYCH
-szybkie wyszukiwanie element o danym kluczu O(h), h - wys. drzewa
-szybkie wyszukiwanie następnika / poprzednika O(h) , h - wys. drzewa
-wysokość drzewa wynosi O(n)
Θ(lg(n)) Podstawowe operacje dla pełnego drzewa
Θ(n) Podstawowe operacje dla drzewa o jednej gałęzi
O(h) Podstawowe operacje dla drzewa o wys. h
DRZEWA CZERWONO-CZARNE
-szybkie wyszukiwanie element o danym kluczu O(h), h - wys. drzewa
-szybkie wyszukiwanie następnika / poprzednika O(h) , h - wys. drzewa
-wysokość drzewa wynosi O(lg(n))
O(lg(n)) Podstawowe operacje dla drzewa czerwono-czarnego
B-DRZEWA
-szybkie wyszukiwanie element o danym kluczu O(h), h - wys. drzewa
-szybkie wyszukiwanie następnika / poprzednika O(h) , h - wys. drzewa
-wysokość drzewa wynosi O(lg(n))
-wysokość drzewa wynosi O(lgt((n+1)/2)), t>1 - minimalny stopień drzewa
…
KOPCE
Make-Heap() tworzy i zwraca nowy, pusty kopiec
Insert(H, x) wstawia do kopca H węzeł x o danym kluczu key
Minimum(H) zwraca wskaźnik do węzła w kopcu H, który zawiera minimalny klucz
Extract-Min(H) usuwa węzeł o minimalnym kluczu, zwracając jednocześnie wskaźnik do tego węzła
Union(H1, H2) tworzy i zwraca nowy kopiec powstały z kopców H1 i H2 (które niszczy)
Decrease-Key(H, x, k) nadaje kluczowi w węźle x z kopca H nową wartość k, nie większą od bieżącej
Delete(H, x) usuwa węzeł x kopca H
KOPCE BINARNE
Θ(1) Make-Heap
Θ(lg(n)) Insert
Θ(1) Minimum
Θ(lg(n)) Extract-Min
Θ(n) Union
Θ(lg(n)) Decrease-Key
Θ(lg(n)) Delete
KOPCE DWUMIANOWE
Θ(1) Make-Heap
O(lg(n)) Insert
O(lg(n)) Minimum
Θ(lg(n)) Extract-Min
O(lg(n)) Union
Θ(lg(n)) Decrease-Key
Θ(lg(n)) Delete
KOPCE FIBONACCIEGO
Θ(1) Make-Heap
Θ(1) Insert
Θ(1) Minimum
O(lg(n)) Extract-Min
Θ(1) Union
Θ(1) Decrease-Key
O(lg(n)) Delete
STOSY
O(1) Push / Pop (dodaje / usuwa element)
O(1) Stack-Empty (sprawdza czy stos jest pusty)
KOLEJKI
O(1) Enqueue / Dequeue (dodaje / usuwa element)
LISTY
Θ(n) List-Search (wyznacza pierwszy element o danym kluczu)
Θ(n) List-Delete (usuwa element o danym kluczu, zawiera List-Search)
O(1) List-Insert (wstawia element o danym kluczu)