Download - [6] Compl Medie
-
Proiectarea algoritmilor: complexitatea medie
Dorel Lucanu
Faculty of Computer ScienceAlexandru Ioan Cuza University, Iasi, Romania
PA 2014/2015
D. Lucanu (FII - UAIC) Complexitatea medie PA 2014/2015 1 / 44
-
Outline
1 Timpul mediu: algoritmi deterministiQuicksort determinist
2 Timpul mediu: algoritmi probabilistiAgoritmi nedeterministiAlgoritmi probabilistiQuicksort probabilist
3 k-mediana
D. Lucanu (FII - UAIC) Complexitatea medie PA 2014/2015 2 / 44
-
Timpul mediu: algoritmi deterministi
Plan
1 Timpul mediu: algoritmi deterministiQuicksort determinist
2 Timpul mediu: algoritmi probabilistiAgoritmi nedeterministiAlgoritmi probabilistiQuicksort probabilist
3 k-mediana
D. Lucanu (FII - UAIC) Complexitatea medie PA 2014/2015 3 / 44
-
Timpul mediu: algoritmi deterministi
Motivatie
Fie P o problema, p P instanta a problemei P, A un algoritm carerezolva P.
Reamintim formula pentru complexitatea n cazul cel mai nefavorabil:TA(n) = sup{TA(p) | p P g(p) = n}
Uneori, numarul instantelor p cu g(p) = n pentru care TA(p) = TA(n) sauTA(p) are o valoare foarte apropiata de TA(n) este foarte mic.
Pentru aceste cazuri este preferabil sa calculam comportarea n medie aalgoritmului.
D. Lucanu (FII - UAIC) Complexitatea medie PA 2014/2015 4 / 44
-
Timpul mediu: algoritmi deterministi
Exemplu de variabila aleatorie: aruncarea a doua zaruri
Experiment: aruncarea a doua zaruriV (experiment) = suma punctelor de pe fetele superioare
Sursa: http://hyperphysics.phy-astr.gsu.edu/hbase/math/dice.html
pi = P(V = xi ) - probabilitatea cu care V ia valoare xiMedia variabilei aleatorii: M(V ) =
i xi pi
D. Lucanu (FII - UAIC) Complexitatea medie PA 2014/2015 5 / 44
-
Timpul mediu: algoritmi deterministi
Exemplu de variabila aleatorie: aruncarea a doua zaruri(cont.)
M(V ) = 7
D. Lucanu (FII - UAIC) Complexitatea medie PA 2014/2015 6 / 44
-
Timpul mediu: algoritmi deterministi
Definitie
Pentru a putea calcula comportarea n medie este necesar sa privimmarimea TA(p) ca fiind o variabila aleatorie:
o experienta = executia algoritmului pentru o instanta p,
valoarea experientei = durata executiei algoritmului pentru instantap) si sa precizam legea de repartitie a acestei variabile aleatorie.
Apoi, comportarea n medie se calculeaza ca fiind media acestei variabilealeatoare (consideram numai cazul timpului de executie):
TmedA (n) = M({TA(p) | p P g(p) = n})Daca multimea valorilor variabilei aleatoare TA(p) = {x0, x1, . . . } estefinita sau numarabila si probabilitatea ca TA(p) = xi este pi , atunci mediavariabilei aleatorie TA (timpul mediu de executie) este:
TmedA (n) =i
xi pi
D. Lucanu (FII - UAIC) Complexitatea medie PA 2014/2015 7 / 44
-
Timpul mediu: algoritmi deterministi
Exemplu
Consideram problema cautarii unui element ntr-o secventa de numerentregi:
Problema P1Intrare: n, a = (a0, . . . , an1), z , toate numere ntregi.
Iesire: poz =
{min{i | ai = z} daca {i | ai = z} 6= ,1 altfel.
Presupunem ca secventa (a0, . . . , an1) este memorata n tabloul a.Consideram ca dimensiune a problemei P1 numarul n al elementelor dinsecventa n care se cauta.
D. Lucanu (FII - UAIC) Complexitatea medie PA 2014/2015 8 / 44
-
Timpul mediu: algoritmi deterministi
Algoritm pentru P1
Algoritmul A1 descris de urmatorul program rezolva P1:
//@input: un tablou a cu n elemente, z
//@output: pozitia primului element din a egal cu z,
// -1 daca nu exista un astfel de element
i = 0;
while (a[i] != z) && (i < n-1) {
i = i+1
if (a[i] = z) poz = i;
else poz = -1;
D. Lucanu (FII - UAIC) Complexitatea medie PA 2014/2015 9 / 44
-
Timpul mediu: algoritmi deterministi
Timpul mediu pentru A1
Multimea valorilor variabilei aleatorii TA1 (p) este {3i + 2 | 1 i n} (s-aunumarat doar atribuirile si comparatiile).In continuare trebuie sa stabilim legea de repartitie. Facem urmatoarelepresupuneri:
probabibilitatea ca z {a0, . . . , an1} este q siprobabilitatea ca z sa apara prima data pe pozitia i 1 este q
n(indicii i
candideaza cu aceeasi probabilitate pentru prima aparitie a lui z).
Rezulta ca probabilitatea ca z 6 {a0, . . . , an1} este 1 q. Acum probabilitateaca TA(p) = 3i + 2 (poz = i 1) este q
n, pentru 1 i < n, iar probabilitatea ca
TA(p) = 3n + 2 este pn =q
n+ (1 q).
Timpul mediu de executie este:
TmedA (n) =n
i=1
pixi =n1i=1
q
n (3i + 2) + (q
n+ (1 q)) (3n + 2)
= 3n 3nq2
+3q
2+ 2
Pentru q = 1 (z apare totdeauna n secventa) avem TmedA (n) =3n
2+
7
2si pentru
q =1
2avem TmedA (n) =
9n
4+
11
4.
D. Lucanu (FII - UAIC) Complexitatea medie PA 2014/2015 10 / 44
-
Timpul mediu: algoritmi deterministi Quicksort determinist
Plan
1 Timpul mediu: algoritmi deterministiQuicksort determinist
2 Timpul mediu: algoritmi probabilistiAgoritmi nedeterministiAlgoritmi probabilistiQuicksort probabilist
3 k-mediana
D. Lucanu (FII - UAIC) Complexitatea medie PA 2014/2015 11 / 44
-
Timpul mediu: algoritmi deterministi Quicksort determinist
Quicksort: descriere
Este proiectat pe paradigma divide-et-impera.Se considera o multime peste care este definita o relatie de ordine liniara = {ai | ai > x}
4 sorteaza recursiv S< si S>5 ntoarce secventa S
D. Lucanu (FII - UAIC) Complexitatea medie PA 2014/2015 12 / 44
-
Timpul mediu: algoritmi deterministi Quicksort determinist
Quicksort: partitionarea
Presupunem ca S este memorata ntr-un tablou a.
Se determinarea prin interschimbari a unui indice k cu proprietatile:
p k q si a[k] = x ;i : p i k = a[i ] a[k];j : k < j q = a[k] a[j ];
Partitionarea tabloului se face prin interschimbari care mentin invarianteproprietati asemanatoare cu cele de mai sus. Se considera doua variabileindex: i cu care se parcurge tabloul de la stanga la dreapta si j cu care separcurge tabloul de la dreapta la stanga. Initial se ia i = p + 1 si j = q.Proprietatile mentinute invariante n timpul procesului de partitionare sunt:
i : p i < i = a[i ] x (1)si
j : j < j q = a[j ] x (2)D. Lucanu (FII - UAIC) Complexitatea medie PA 2014/2015 13 / 44
-
Timpul mediu: algoritmi deterministi Quicksort determinist
Quicksort: partitionarea
Presupunem ca la momentul curent sunt interogate elementele a[i] si a[j]cu i < j . Distingem urmatoarele cazuri:
1 a[i ] x . Transformarea i = i+1 pastreaza (1).2 a[j ] x . Transformarea j = j-1 pastreaza (2).3 a[i ] > x > a[j ]. Daca se realizeaza interschimbarea a[i] a[j] si se
face i = i+1 si j = j-1, atunci ambele predicate (1) si (2) suntpastrate.
Operatiile de mai sus sunt repetate pana cand i devine mai mare decat j .Considerand k = i 1 si interschimband a[p] cu a[k] obtinempartitionarea dorita a tabloului.
D. Lucanu (FII - UAIC) Complexitatea medie PA 2014/2015 14 / 44
-
Timpul mediu: algoritmi deterministi Quicksort determinist
Quicksort: algoritmul de partitionare
@input: a = (a[p], . . . , a[q])@output: k, a cu proprietatea i : p i k = a[i ] a[k] si j :k < j q = a[k] a[j ]partitioneaza(a, p, q, k) {
x = a[p] ;
i = p + 1; j = q;
while (i j) {if (a[i] x) i = i+1;if (a[j] x) j = j-1;if ((i < j) && (a[i] > x) && (x > a[j])) {
swap(a, i, j);
i = i+1;
j = j-1;
}
}
k = i-1; a[p] = a[k]; a[k] = x;
}
D. Lucanu (FII - UAIC) Complexitatea medie PA 2014/2015 15 / 44
-
Timpul mediu: algoritmi deterministi Quicksort determinist
Quicksort: algoritm
Dupa sortarea recursiva a subtablourilor a[p..k 1] si a[k + 1..q] seobserva ca tabloul este sortat deja. Astfel partea de asamblare a solutiiloreste vida.
@input: a = (a[p], . . . , a[q])@output: elementele secventei a n ordine crescatoareqsort(a, p, q) {
if (p < q) {
partitioneaza(a, p, q, k)
qSort(a, p, k)
qSort(a, k+1, q)
}
}
D. Lucanu (FII - UAIC) Complexitatea medie PA 2014/2015 16 / 44
-
Timpul mediu: algoritmi deterministi Quicksort determinist
Quicksort: timpul n cazul cel mai nefavorabil
Cazul cel mai nefavorabil se obtine atunci cand la fiecare partitionare seobtine una din subprobleme cu dimensiunea 1.
Deoarece operatia de partitionare necesita O(q p) comparatii, rezulta capentru acest caz numarul de comparatii este O(n2).
Acest rezultat este oarecum surprinzator, avand n vedere ca numelemetodei este sortare rapida.
Asa cum vom vedea, ntr-o distributie normala cazurile pentru careQuickSort executa n2 comparatii sunt rare, fapt care conduce la ocomplexitate medie foarte buna a algoritmului.
D. Lucanu (FII - UAIC) Complexitatea medie PA 2014/2015 17 / 44
-
Timpul mediu: algoritmi deterministi Quicksort determinist
Quicksort: timpul mediu
Presupunem ca q + 1 p = n (lungimea secventei) si ca probabilitatea ca pivotulx sa fie al k-lea element este
1
n(fiecare element al tabloului poate fi pivot cu
aceeasi probabilitate1
n). Rezulta ca probabilitatea obtinerii subproblemelor de
dimensiuni k p = i 1 si q k = n i este 1n
. In procesul de partitionare, un
element al tabloului (pivotul) este comparat cu toate celelalte, astfel ca suntnecesare n 1 comparatii. Acum numarul mediu de comparatii se calculeaza prinformula:
Tmed(n) =
(n 1) +1
n
ni=1
(Tmed(i 1) + Tmed(n i)) ,daca n 11 ,daca n = 0
Teorema
Complexitatea medie a algoritmului QuickSort este O(n log2 n).
D. Lucanu (FII - UAIC) Complexitatea medie PA 2014/2015 18 / 44
TeaHighlight
TeaHighlight
-
Timpul mediu: algoritmi probabilisti
Plan
1 Timpul mediu: algoritmi deterministiQuicksort determinist
2 Timpul mediu: algoritmi probabilistiAgoritmi nedeterministiAlgoritmi probabilistiQuicksort probabilist
3 k-mediana
D. Lucanu (FII - UAIC) Complexitatea medie PA 2014/2015 19 / 44
-
Timpul mediu: algoritmi probabilisti Agoritmi nedeterministi
Plan
1 Timpul mediu: algoritmi deterministiQuicksort determinist
2 Timpul mediu: algoritmi probabilistiAgoritmi nedeterministiAlgoritmi probabilistiQuicksort probabilist
3 k-mediana
D. Lucanu (FII - UAIC) Complexitatea medie PA 2014/2015 20 / 44
-
Timpul mediu: algoritmi probabilisti Agoritmi nedeterministi
Definitie
Activitatea unui algoritm nedeterminist se desfasoara n doua etape: ntr-o primaetapa se ghiceste o anumita structura S si n etapa a doua se verifica daca Ssatisface o conditia de rezolvare a problemei. Putem adauga puteri magice deghicire unui limbaj de programare adaugandu-i o functie de forma:
random(N) care ntoarce un numar aleatoriu din multimea{0, 1, . . . , n 1}.
Pentru a sti daca verificarea s-a terminat cu succes sau nu adauga si douainstructiuni de terminare:
success care semnaleaza terminarea verificarii (si a a algoritmului) cusucces, si
failure care semnaleaza terminarea verificarii (si a a algoritmului) farasucces.
Aceasta definitie a algoritmilor nedeterministi este strans legata de rezolvareaproblemelor de decizie. Reamintim ca, n general, orice problema poate fi redusala rezolvarea unei probleme de decizie.
D. Lucanu (FII - UAIC) Complexitatea medie PA 2014/2015 21 / 44
-
Timpul mediu: algoritmi probabilisti Agoritmi nedeterministi
Functia random n Alk
Urmatorul exemplu este un generator de numere pseudo-aleatorii dincartea The C Programming Language de Kernighan and Ritchie.
rand() {
random_seed = random_seed * 1103515245 +12345;
return (random_seed / 65536) % 32768;
}
In Alk este implementata varianta care ntoarce valoarea calculata modulon, unde n este parametrul functiei.
D. Lucanu (FII - UAIC) Complexitatea medie PA 2014/2015 22 / 44
-
Timpul mediu: algoritmi probabilisti Agoritmi nedeterministi
Agoritmi nedeterministi: exemplu
exp() {
return (1 - x[0])*x[1] + x[0]*(1 - x[2]);
}
x[0] = random(2);
x[1] = random(2);
x[2] = random(2);
if (exp() == 1) success;
else failure;
D. Lucanu (FII - UAIC) Complexitatea medie PA 2014/2015 23 / 44
-
Timpul mediu: algoritmi probabilisti Agoritmi nedeterministi
Agoritmi nedeterministi: demo
$ krun programs/ex1.alk -cST="x |-> { .Map }" -cSEED="1214"
failure ;
x |-> { 0 |-> 0 1 |-> 0 2 |-> 0 }
$ krun programs/ex1.alk -cST="x |-> { .Map }" -cSEED="1212"
success ;
x |-> { 0 |-> 0 1 |-> 1 2 |-> 1 }
$
D. Lucanu (FII - UAIC) Complexitatea medie PA 2014/2015 24 / 44
-
Timpul mediu: algoritmi probabilisti Algoritmi probabilisti
Plan
1 Timpul mediu: algoritmi deterministiQuicksort determinist
2 Timpul mediu: algoritmi probabilistiAgoritmi nedeterministiAlgoritmi probabilistiQuicksort probabilist
3 k-mediana
D. Lucanu (FII - UAIC) Complexitatea medie PA 2014/2015 25 / 44
-
Timpul mediu: algoritmi probabilisti Algoritmi probabilisti
Definitii
Exista doua puncte de vedere:
1. algoritmul probabilist este vazut ca un algoritm nedeterministpentru care exista o distributie de probabilitate peste alegerilenedetermiste2. algoritmul probabilist este un algoritm care are o intraresuplimentara ce consta ntr-o secventa de biti aleatorii;
e echivalent cu a spune ca algoritmul probabilist consta n o multimede algoritmi determinissti din care un algoritm este ales aleatoriupentru o intrare datapentru o intrare x a problemei date, calculele algoritmului probabilistpot diferi n functie de e secventa actuala de biti aleatori
Aceasta diferenta poate fi proiectata n complexitate sau iesire:
timpul de executie vazut ca o variabila aleatorieiesirea vazuta ca o variabila aleatorie
La acest curs considera doar prima varianta (numiti si algoritmi LasVegas).
D. Lucanu (FII - UAIC) Complexitatea medie PA 2014/2015 26 / 44
-
Timpul mediu: algoritmi probabilisti Algoritmi probabilisti
Timpul mediu de executie al algoritmilor probabilisti
ProbA,x(C ) = probabilitatea cu care algoritmul A executa calculul Cpentru intrarea x
Time(C ) = timpul necesar lui A ca sa execute C
y iesirea pentru intrarea xAC (x) iesirea calculata de C pentru intrarea x
timpul mediu de executie a lui A pentru intrarea x esteExp-TimeA(x) = M[Time] =
C ,AC (x)=y
ProbA,x(C ) Time(C ).Time este variabila aleatorie.
timpul mediu de executie a lui A n cazul cel mai nefavorabil esteExp-TimeA(n) = max{Exp-TimeA(x) | g(x) = n}
D. Lucanu (FII - UAIC) Complexitatea medie PA 2014/2015 27 / 44
-
Timpul mediu: algoritmi probabilisti Quicksort probabilist
Plan
1 Timpul mediu: algoritmi deterministiQuicksort determinist
2 Timpul mediu: algoritmi probabilistiAgoritmi nedeterministiAlgoritmi probabilistiQuicksort probabilist
3 k-mediana
D. Lucanu (FII - UAIC) Complexitatea medie PA 2014/2015 28 / 44
-
Timpul mediu: algoritmi probabilisti Quicksort probabilist
Randomized Quicksort
- exemplul canonic pentru algoritmii Las Vegas
Algoritmul RQSIntrare: S = {a0, . . . , an1}Iesire: elementele ai n ordine crescatoare
1 daca n = 1 ntoarce a0,
2 altfel alege aleatoriu uniform k {0, . . . , n 1}3 calculeaza
S< = {ai | ai < ak}S= = {ai | ai = ak}S> = {ai | ai > ak}
4 sorteaza recursiv S< si S>5 ntoarce secventa S
D. Lucanu (FII - UAIC) Complexitatea medie PA 2014/2015 29 / 44
-
Timpul mediu: algoritmi probabilisti Quicksort probabilist
Analiza algoritmului RQS
Fie functia rank astfel ncat arank(0) . . . arank(n1).
Definim Xij =
{1 arank(i) si arank(j) sunt comparate
0 altfelCu ajutorul lui Xij se numara comparatiile dintre arank(i) si arank(j).
Xij este variabila aleatorie
Numarul mediu de comparatii este
M[n1
i=0
j>i Xij ] =
n1i=0
j>i M[Xij ].
D. Lucanu (FII - UAIC) Complexitatea medie PA 2014/2015 30 / 44
-
Timpul mediu: algoritmi probabilisti Quicksort probabilist
Analiza algoritmului RQS
pij probabiltatea ca arank(i) si arank(j) sa fie comparate ntr-o executie
M[Xij ] = pij 1 + (1 pij) 0 = pijpij =
2
j i + 1 (probabilitatea ca arank(i) sau arank(j) sa fie ales pivot)
n1i=0
j>i
pij =n1i=0
j>i
2
j i + 1
n1i=0
nk=1
2
k
= 2n
i=1
nk=1
1
k
= 2nn
k=1
1
k
D. Lucanu (FII - UAIC) Complexitatea medie PA 2014/2015 31 / 44
-
Timpul mediu: algoritmi probabilisti Quicksort probabilist
Analiza algoritmului RQS
Teorema
Numarul mediu de comparatii ntr-o executie al algoritmului RQS este celmult 2nHn = O(n log n).
D. Lucanu (FII - UAIC) Complexitatea medie PA 2014/2015 32 / 44
-
k-mediana
Plan
1 Timpul mediu: algoritmi deterministiQuicksort determinist
2 Timpul mediu: algoritmi probabilistiAgoritmi nedeterministiAlgoritmi probabilistiQuicksort probabilist
3 k-mediana
D. Lucanu (FII - UAIC) Complexitatea medie PA 2014/2015 33 / 44
-
k-mediana
k-mediana: definitie
Definitie
Fie S o lista cu n elemente dintr-o multime univers total ordonata.k-mediana este cel de-al k-lea element din lista sortata a elementelor dinS . In alte cuvinte, k-mediana este un element x {a[0], . . . , a[n 1]} cuproprietatile |{i | 0 i < n a[i ] < x}| < k si|{i | 0 i < n a[i ] x}| k (daca toate lelementele din S suntdistincte, atunci avem egalitate n ultima relatie).
D. Lucanu (FII - UAIC) Complexitatea medie PA 2014/2015 34 / 44
-
k-mediana
Aplicatie: mediana unei multimi de puncte
D. Lucanu (FII - UAIC) Complexitatea medie PA 2014/2015 35 / 44
-
k-mediana
k-mediana: problema
Presupunem S memorata ntr-un tablou.Consideram urmatoarea problema:
Input un tablou (a[i ] | 0 i < n) si un numar k {0, 1, . . . , n 1},Output k-mediana
Evident, orice algoritm de sortare rezolva problema de mai sus. Deoarececerintele pentru selectie sunt mai slabe decat cele de la ordonare, se punefiresc ntrebarea daca exista algoritmi mai performanti decat cei utilizati lasortare.
D. Lucanu (FII - UAIC) Complexitatea medie PA 2014/2015 36 / 44
-
k-mediana
k-mediana: descriere algoritm
Conditia pe care trebuie sa o satisfaca la iesire tabloul a este formulata de:
(i)(i < k = a[i ] a[k]) (i > k = a[i ] a[k])
Fie j o pozitie n a astfel ncat:
(i)(i < j = a[i ] a[j ]) (i > j = a[i ] a[j ])
Un asemenea j poate fi obtinut cu algoritmul de partitionare de laquickSort. Daca j = k atunci problema este rezolvata. Daca j < katunci cel de-al k-lea cel mai mic element trebuie cautat n subtabloula[j+1..n], iar daca j > k atunci cel de-al k-lea cel mai mic elementtrebuie cautat n subtabloul a[1..j-1].
D. Lucanu (FII - UAIC) Complexitatea medie PA 2014/2015 37 / 44
-
k-mediana
k-mediana: algoritmul recursiv
Aceasta conduce la urmatoarea formulare recursiva a algoritmului deselectare:
@input: un tablou a cu n elemente, 0 k < n@output: k-mediana
selecteaza(a, p, q, k) {
partitioneaza(a, p, q, j);
if (j == k) return a[k];
if (j < k) selecteaza(a, j + 1, q, k);
else selecteaza(a, p, j - 1, k);
}
D. Lucanu (FII - UAIC) Complexitatea medie PA 2014/2015 38 / 44
-
k-mediana
k-mediana: algoritmul nerecursiv
Descrierea recursiva nu este avantajoasa deoarece produce un consum dememorie suplimentara (stiva apelurilor recursive) ce poate fi eliminat prinderecursivare:
@input: un tablou a cu n elemente, 0 k < n@output: k-mediana
selecteaza(a, n, k) {
p = 0; 1 = n-1;
repeat
partitioneaza(a, p, q, j);
if (j < k) p = k1 + 1;
if (k < j) q = k1 - 1;
until (j == k);
return a[k];
}
D. Lucanu (FII - UAIC) Complexitatea medie PA 2014/2015 39 / 44
-
k-mediana
k-mediana: analiza
Analiza algoritmului selecteaza este asemanatoare cu cea a algoritmuluiquickSort. In cazul cel mai nefavorabil necesita O(n2) timp, iar pentrucomplexitatea medie se cunoaste urmatorul rezultat:
Teorema
Complexitatea timp medie a algoritmului Selecteaza este O(n). Maiprecis, numarul de comparatii este aproximativ:
n + k log(nk
)+ (n k) log
(n
n k).
D. Lucanu (FII - UAIC) Complexitatea medie PA 2014/2015 40 / 44
-
k-mediana
Mediana in general: un rezultat ajutator
Proprietate: Fie data o bara de lungime 1, care se taie arbitrar n doua. Lungimea
medie a bucatii mai lungi este3
4.
Spatiul continuu: Consideram variabila aleatorie Y = max(u, 1 u).M(Y ) =
10 M(Y | Y = u)du =
12
0 (1 u)du + 1
12
udu =3
4
Spatiul discret: se mparte bara n n parti egale de lungime1
n
n par: lungimile segmentelor mai lungi suntk
n, k =
n
2+ 1, . . . , n 1, cu probabilitatea 2
n 1 . Rezulta media egala cun1k=n/2+1
k
n 2n 1 =
3n 64(n 1)
3
4
n impar: lungimile segmentelor mai lungi suntk
n, k =
n + 1
2, . . . , n 1, cu probabilitatea 2
n 1 . Rezulta media egala cun1k=(n+1)/2
k
n 2n 1 =
3n 14n
34
La limita se obtine n ambele cazuri3
4.
Concluzie: daca se mparte n doua un tablou de lungime n, lungimea celui mare
subtablou este3
4n.
D. Lucanu (FII - UAIC) Complexitatea medie PA 2014/2015 41 / 44
-
k-mediana
Mediana in general: analiza
Intuitiv: Exp-Time(n) (n 1) + Exp-TimeA( 34n)Formal: Presupunem ca pivotul este ales aleatoriu.AvemExp-Time(n) = maxk Exp-Time(n, k)
Afirmam ca Exp-Time(n) 4n. Demonstram prin inductie.Exp-Time(n) (n 1) +n1i=n/2 Exp-Time(i) =(n 1) + M(Exp-Time(n2 ), . . . ,Exp-Time(n 1))Ipoteza inductiva: Exp-Time(i) 4i , i = n/2, . . . , n 1Avem Exp-Time(n) (n 1) +M(4n2 , . . . , 4(n 1)) (n 1) + 4 34n < 4n
D. Lucanu (FII - UAIC) Complexitatea medie PA 2014/2015 42 / 44
-
k-mediana
Un algoritm determinist liniar
[Manuel Blum, Robert W. Floyd, Vaughan Pratt, Ronald L. Rivest, andRobert E. Tarjan. 1972. Linear time bounds for median computations.]
1 grupeaza tabloul n n5 grupe de 5 elemente si calculeaza medianafiecarei grupe;
2 calculeaza recursiv mediana medianelor p
3 utilizeaza p ca pivot si separa elementele din tablou
4 apeleaza recursiv pentru subtabloul potrivit (n care se aflak-mediana)
D. Lucanu (FII - UAIC) Complexitatea medie PA 2014/2015 43 / 44
-
k-mediana
Un algoritm determinist liniar: analiza
Notatii: T (n, k) timpul pentru cazul cel mai nefavorabil pentru k-mediana,Tn = maxk T (n, k) Pasul 1: O(n)Pasul 2: T (n/5)Pasul 3: O(n)pasul 4: presupunand ca cel putin 310 din tablou este p si ca cel putin 310 dintablu este p, pasul recursiv ia cel mult T ( 7n10 ).nsumand obtinem:
T (n) cn + T ( n5 ) + T ( 7n10 ) cn + c n5 + T ( n52 ) + T ( 7n510 ) + c 7n10 + T ( 7n510 ) + T ( 7
2n102 ) . . . = O(n) (similar
teoremei de master).
Demonstrarea afirmatiei cel putin 310 din tablou este p si ca cel putin 310 dintablou este p:Fie g = n5 .Cel putin d g2 e dintre grupuri (cele cu mediana p) au cel putin trei elemente p.Rezulta ca numarul de elemente p este cel putin 3d g2 e 3n10 .Analog pentru numarul de elemente p.Comparati experimental cei doi algoritmi pentru mediana.
D. Lucanu (FII - UAIC) Complexitatea medie PA 2014/2015 44 / 44
Timpul mediu: algoritmi deterministiQuicksort determinist
Timpul mediu: algoritmi probabilistiAgoritmi nedeterministiAlgoritmi probabilistiQuicksort probabilist
k-mediana