Insertion sort:
n=długość tablicy
T(n)=czas działania algorytmu na n-elementowej tablicy
tj=ilość powtórzeń pętli wenętrznej dla kazdego j
T(n)=c1*n+c2*(n-1)+suma od j=2 do n*c3tj
Wariant optymistyczny: tj=0
T(n)=c1*n+c2*(n-1)<=(c1+c2)*n=c*n; T(n)<=c*n
Wariant pesymistyczny: tj=j-1
T(n)=c1*n+c2*(n-1)+suma od j=2 do n *c3(j-1)=c1n+c2(n-1)+c3*1+n-1/2*(n-1)
=c1n+c2(n-1)+c3*n(n-1)/2
Stwierdzenie: złożoność ins. sort jest: a)optymistyczna-T(n)=O(n); b)pesymistyczna-T
(n)=θ(n^2)
Notacja:
T(n)=O(f(n)) jeżeli istnieją stałe c>0,n0>0 takie, że dla n>n0 T(n)<c*f(n)
T(n)=Ω(f(n)) jeżeli istnieją stałe c>0,n0>0 takie, że dla n>=n0 T(n)>=c*f(n)
T(n)=θ(f(n)) jeżeli T(n)=O(f(n)) oraz T(n)=Ω(f(n)) czyli c2*f(n)<=T(n)<=c1*f(n) dla pewnych c1, c2 oraz n>=n0
HEAP SORT: Czas pesymistyczny sortowania Heap-sort jest θ(nlgn).
Dowód: T(n) - czas heap-sort dla n elementów
T(n)<=O(n)+(n-1)*(c1+O(lgn)) [gdzie O(n)-budowanie kopca,(n-1)-wykonanie pętli sortującej,c1-zmniejszenie kopca,O(lgn)-oszacowanie czasu Heapify]
Def: kopiec binarny jest to drzewo binarne, w którego węzłach są pewne wartości(liczby) i który ma
następujące własności: 1)wszystkie poziomy oprócz ostatniego są wypełnione, ostatni poziom jest wypelniony też
bez luk od lewej do prawej, do pewnego miejsca.2)wartość w każdym węźle jest wieksza lub równa od wartości
wpisanych w jego synach.
TABLICOWA reprezentacja kopca:
poziom 0 - 1 węzeł=2^0=1
poziom 1 - 2 węzły-2^1=2
poziom 2 - 4 węzły-2^2=4
poziom h - 2^h węzły
poziom h+1 - 2^h+1 węzły
|_|_|_|i/2|_|_| i |_|_|2i|2i+1|_|_|_|
kopiec o n węzłach ma wysokość lgn
Dowód: h-wysokość kopca
2^h<=n<=2^(h+1) -1<2^h+1
h<=lgn<h+1 h=lgn
HEAPIFY: Złożoność pesymistyczna procedury budującej kopiec Build-heap jest O(n) gdzie n-ilość elementów w kopcu. Kopcowanie Heapify - złożoność O(h), h - wysokość kopca.
Kopcowa implementacja kolejki priorytetowej: Def: kolejka priorytetowa S to struktura danych, w której mozna przechowywać pewne elementy posiadające priorytety(wartości całkowite)Swierdzenie:Złożoność pesymistyczna operacji kolejki reprezentowanej w kopcu jest:A)maximum-θ(1),B)extract-max-θ(lgn)C)insert-θ(lgn) [n-ilość elementów w kolejce] Dowód:Operacje polegają na przejściu w kopcu od góry do dołu, lub owdrotnie, na każdym poziomie skończona ilość operacji, poziomów jest lgn.
Porównanie implementacji kolejki priorytetowej:
Implenetacja/Maximum/Extract-max/Insert
Kopce / θ(1) / θ(lgn) / θ(lgn)
tab. nieuporz./ θ(n) / θ(n) / θ(1)
tab.uporz. / θ(1) / θ(1) / θ(n)
lista / θ(1) / θ(1) / θ(n)
QUICK-SORT: Pesymistyczna zlożoność czasowa Q-S jest θ(n^2) DOWÓD:Ω(n^2): T(n)>= θ(n)+ θ(n-1)+ θ(n-2)+ θ(n-3)+ θ(n-2)+ θ(1)>=c1n+c1(n-1)+c1(n-2)+c1(n-3)+c1(n-4)+c1(n-5)+c1*1>=c1n+(n-1)+(n-2)+(n-3)+(n-4)+(n-5)+1=c1*(n+1)n/2>=c1/2*n^2=Ω(n^2)
Randomized-Quick-Sort: Złożoność oczekiwana jest O(nlgn) zakładając, że procedura losująca z jednakowym prawdopodobieństwem wybiera każdy element tablicy.DOWÓD:element wyznaczający podział:a)jest największy, to podział n-1:1 b)jest drugi co do wielkości n-1:1 c)jest trzeci co do wielkości n-2:2 d)jest najmniejszy 1:n-1 T(n) - pczekiwany (średni) czas RQS na n-elementowej tablicy. T(n)=θ(n)+1/n(suma od k=1 do n-1(T(k)+T(n-k))+T(1)+T(n-1)) [gdzie: θ(n)-partition, suma i T(1) - możliwe przypadki podziału]. Czas pesymistyczny - O((n-1)^2). T(n)<=θ(n)+1/n*suma od k=1 do n-1(T(k)+T(n-k))+O(n)+O(n). T(n)<=θ(n)+2/n*suma od k=1 do n-1*T(k).COUNTING SORT:Złożoność pesymistyczna CS jest θ(k+n). Wniosek:jeżeli k=O(n) czy wręcz k=O(1) to θ(k+n) = θ(n) czyli CS działa w czasie θ(n) RADIX-SORT:złożoność pesymistyczna RS + CS jest θ(dk+dn) gdzie :d-ilosc cyfr, k-zakres wartości cyfr(0-9), n-ilość sortowanych liczb d-cyfrowych WNIOSEK: jeżeli d,k=O(n) lub O(1) to RS działa liniowo θ(n). O(n)-sortowanie przy pewnych założeniach o wartościach, O(nlgn)-ogólne sortowania przez porównania
LISTY: to zbiór elementów ustawionych w jakiejś kolejności. Typowa implementacja listy: dowiązaniowa,tablicowa.STWIERDZENIE:Złożność pesymistyczna operacji na listach dowiązaniowych:A)wstaw- θ(1),B)usuń- θ(1),C)szukaj- θ(n) [gdzie n-ilosc elementów na liście] STOS: to struktura danych, w której mozna przechowywać pewne elementy KOLEJKA: to struktura danych, w której można przechowywać pewne elementy STWIERDZENIE:Złożoność pesymistyczna operacji kolejkowych oraz stosowych jest θ(1)(dla implementacji tablicowych oraz dowiązaniowych)HASZOWANIE:Pesymistyczna złożoność operacji na tablicy haszowanejz łańcuchową metodą rozwiązywania konfliktów jest:A)wstaw= θ(1) B)szukaj= θ(n)[wszystkie elementy mogą być na jednej liście, n-ilość elementów w tablicy] C)usuń= θ(1)[przy rozsądnej implementacji] STWIERDZENIE: oczekiwany czas szukania zakończonego porażką w tablicy haszowań z łańcuchową metodą rozw. konf. przy założeniu równomiernego haszowania jest O(1+α) gdzie α=n/m [α-współczynnik wypełnienia, n-ilość elementów w tablicy, m-rozmiar tablicy] Z ADRESOWANIEM OTWARTYM: Złożoność pesymistyczna wstawiania i szukania w haszowaniu z ard. otw. jest θ(n), gdzie n-ilość zajętych pozycji w tablicy. DOWÓD: może byc tak, że zanim dojdziemy do szukanego klucza(do dowolnej pozycji przy wstawianiu) przejdziemy przez wszystkie zajęte pozycje. TWIERDZENIE: każdy algor. sort. przez porównania ma złożoność pes. Ω(nlgn), gdzie n-ilosc sortowanych elemetów. DOWÓD: algorytm przedstawiony jako drzewo decyzyjne:A)czas pes. alg.>= wysokość drzewa B)ilość liści>= n!(ilość przodków) C)drzewo o wysokości h ma co najmniej 2^h liści. n!<=ilość liści<=2^h, 2^h>=n! WNIOSEK: HEAP-SORT ma złożonośc θ(nlgn) i jest optymalnym alg. sortującym. Każdy alg. sort. przez porównania ma złoż. oczekiwaną Ω(nlgn). BST: STWIERDZENIE: Złoż. pes. wstawiania, szukania, usuwania w drzewach bst jest: A)θ(n)-gdzie n-ilość węzłów w drzewie B)θ(h)-gdzie h-wysokość drzewa DOWÓD:-może być konieczne zejście do najnizszego liścia w drzewie, -drzewo o n węzłach może mieć wysokość n-1= θ(n) WNIOSEK: oczekiwana zł. operacji wstaw/usuń/szukaj na losowo skonstruowanym BST jest O(lgn) RED-BLACK TREE: zł. pes. operacji wsat/szukaj/usuń w drzewie cz-cz o n węzłach jest O(lgn) DOWÓD: procedury polegające na przejściu od korzenia do liścia(w najgorszym razie i spowrotem w czasie poprawiania. wysokość drzewa O(lgn)).