ASD ściąga z sortowania 1

Log rr; n^A(l/2); n; n*log n; n^A2; n^A3; 2^An; nl Metoda Sekwencyjna (Wyszukiwanie w ciągu uporządkowanym) - W najgorszym razie 2 + (n-1) porównań.Czyli W(n) = O(n). A(n) = n/2 +c, gdzie cc 2

Skoki co 4 - koszt pesymistyczny - 2+[n/4] + 3 (czyli: 2+(n/k]+[k-l]) Skoki co k - koszt pesymistyczny najmniejszy dla k=n^A(l/2)

Algorytm biselccji - k =[ Ig n] (największa wartość k - I. wykonanych iteracji pętli)

T(min_maxl,n) = 2n-2 (ciąg uporządkowany - szukamy min i max) -algorytm naiwny

Mlrwnax2 - A(n) = 2n - Ig n +c Min_max3 - 3n/2 -2 porównań

Min_max4 - Op. Dom. - porównywanie elementów; T(min_max4, n) =

UU>z2.

Optymalny dla wyszukiwania min_max i!

2'gi największy - T(n) - 2n -3 - algorytm naiwny

Turniej - [n-1] porównań (budowa drzewa); [Ig n -1] - wybrania 2'giego

największego;

T(n)= n ± lo n -2

STOS - push (dodanie na koniec), top(zwrocenie ost.), pop(zdjecie), empty KOLEJKA - inject(dodanie na koniec),...........7

k-ty największy (ciąg uporządkowany) - HOARE - T(SPLIT, n ) = n-1 = «(n)    A(n,k) = O(n)

SelectionSort - w n-1 przebiegach; T(n) = n-1 (O(n)) (dominuje przestawienie) T(n) = n*(n-l)/2 - dominuje porównanie fOfn^A2iJ InsertionSort - w n-1 przebiegach; sortuje w miejscu; IV4*n^A2łOfnn-Ofn^A2j

QuickSort - SPLIT dla n elementowego ciągu wynosi n-1 porównań A(nl=cn lo n

Drzewo decyzyjne - co najmniej wysokość Rob n! 1; co najmniej Tlog n! 1 porównań w najgorszym wypadku; W(n) z I" n fg n 1 CountSort - 0(k+n) -RadixSort - 0{d*n) - n liczb o d cyfrach Inorder - lewe, korzeń, prawe Preorder - korzeń, lewa, prawe Postorder - lewe, prawe, korzeń BST - member - A(n)<=klBn; k - stała minimum - 0(n)^(fln insert -A(n) = 0(lg n)

UTWORZENIE - 0(n la n), najgorzej (n^A2)

WYWAŻONE (AVL) - dla wszystkich jego wierzchołków, wysokości lewego i prawego paddrzewa różnią się co najwyżej o 1

h s 2 Ig Nh; Koszty operacji min, member, insert i delete są rzędu Oflo

ni

Jeśli wkładamy element do drzewa AVL, to co najwyżej 1 rotację.

Jeśli usuwamy, to co najwyżej tyła rotacji ile jest poziomów.

HEAP - h- I lafn+11 I: insert I delmin Ofl lofn+11 11.

HeapSort - Koszt = koszt utworzenia kopca + n * Odo ni - Ofn lo nl