Algorytmy ściąga, Insertion sort:


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



Wyszukiwarka