Info & MatematicăMatematică şi informatică pe pâine…

6 Selectia unui element dintr-un tablou

Putem gasi cu usurinta elementul maxim sau
minim al unui tablou T. Cum putem
determina insa eficient mediana lui T ?
Pentru inceput, sa definim formal mediana unui tablou.

Un element m al tabloului T[1 .. n] este mediana lui T, daca si numai daca sunt verificate
urmatoarele doua relatii:

#{i  {1, , n} | T[i] < m} < n/2

#{i  {1, , n} | T[i]  m}  n/2

Aceasta definitie tine cont de faptul ca n poate fi par sau impar si ca
elementele din T pot sa nu fie
distincte. Prima relatie este mai usor de inteles daca observam ca

#{i  {1, , n} | T[i] < m} = n - #{i  {1, , n} | T[i]  m}

Conditia

#{i  {1, , n} | T[i] < m} < n/2

este deci echivalenta cu conditia

#{i  {1, , n} | T[i]  m} > n - n/2 = n/2

Algoritmul naiv pentru determinarea
medianei lui T consta in a sorta
crescator tabloul si a extrage apoi elementul din pozitia n/2. Folosind mergesort, de exemplu, acest algoritm necesita un timp in Q(n log n). Putem gasi o metoda mai
eficienta? Pentru a raspunde la aceasta intrebare, vom considera o problema mai
generala.

Fie T
un tablou de n elemente si fie k un intreg, 1  k  n. Problema selectiei consta in gasirea
celui de-al k-lea cel mai
mic element al lui T, adica a
elementul m pentru care avem:

#{i  {1, , n} | T[i] < m} < k

#{i  {1, , n} | T[i]  m}  k

Cu alte cuvinte, este al k-lea element in T, daca tabloul este
sortat in ordine crescatoare. De exemplu, mediana lui T este al  n/2-lea
cel mai mic element al lui T. Deoarece n/2 = (n+1)/2 = (n+1) div 2,
mediana lui T este totodata al ((n+1) div 2)-lea
cel mai mic element al lui T.

Urmatorul algoritm, inca nu pe deplin
specificat, rezolva problema selectiei intr-un mod similar cu quicksort dar si cu binsearch.

function selection(T[1 .. n], k)
{gaseste al k-lea cel mai mic element al lui T;
se presupune ca 1  k  n}
if
n este mic then sorteaza T
return T[k]
p
un element pivot din T[1 .. n]
u
#{i {1, , n} | T[i]
< p}
v
#{i {1, , n} | T[i]
p}
if u k then
array U[1 .. u]
U elementele din T mai mici decat p
{cel de-al k-lea cel mai mic element al lui T este
si cel de-al k-lea
cel mai mic element al lui U}
return selection (U, k)
if v k then {am
gasit!} return p

{situatia
cand u < k si v < k}
array
V[1 .. n-v]
V
elementele din T mai mari
decat p
{cel de-al k-lea cel mai mic element al lui T este

si cel de-al (k-v)-lea cel mai mic
element al lui V}
return
selection(V, k-v)

Care element din T sa fie ales ca pivot? O alegere naturala este mediana lui T, astfel incat U si V sa fie de marimi
cat mai apropiate (chiar daca cel mult unul din aceste subtablouri va fi
folosit intr-un apel recursiv). Daca in algoritmul selection alegerea pivotului se face prin atribuirea

p  selection(T, (n+1) div 2)

ajungem insa la un cerc vicios.

Sa analizam algoritmul de mai sus, presupunand, pentru inceput, ca gasirea
medianei este o operatie elementara. Din definitia medianei, rezulta ca u < n/2
si v  n/2.
Obtinem atunci relatia n-v  n/2.
Daca exista un apel recursiv, atunci tablourile U si V contin
fiecare cel mult n/2
elemente. Restul operatiilor necesita un timp in ordinul lui n. Fie t_m(n)
timpul necesar acestei metode, in cazul cel mai nefavorabil, pentru a gasi al
k-lea cel mai mic element al unui tablou de n elemente. Avem

t_m(n)  O(n) + max{t_m(i) | i  n/2}

De aici se deduce (Exercitiul 7.17) ca t_m  O(n).

Ce facem insa daca trebuie sa tinem cont si
de timpul pentru gasirea pivotului? Putem proceda ca in cazul quicksort-ului si sa renuntam la
mediana, alegand ca pivot primul element al tabloului. Algoritmul selection astfel precizat are timpul
pentru cazul mediu in ordinul exact al lui n.
Pentru cazul cel mai nefavorabil, se obtine insa un timp in ordinul lui n².

Putem evita acest caz cel mai nefavorabil cu timp patratic, fara sa sacrificam
comportarea liniara pentru cazul mediu. Ideea este sa gasim rapid o aproximare
buna pentru mediana. Presupunand n  5,
vom determina pivotul prin atribuirea

p  pseudomed(T)

unde algoritmul pseudomed este:

function pseudomed(T[1 .. n])
{gaseste o aproximare a medianei lui T}
s
n div 5
array
S[1 .. s]
for i 1 to s do
S[i] adhocmed5(T[5i-4 .. 5i])
return
selection(S, (s+1) div 2)

Algoritmul adhocmed5 este elaborat special pentru a gasi mediana a exact cinci
elemente. Sa notam ca adhocmed5
necesita un timp in O(1).

Fie m
aproximarea medianei tabloului T,
gasita prin algoritmul pseudomed. Deoarece
m este mediana tabloului S, avem

#{i  {1, , s} | S[i]  m}  s/2

Fiecare element din S este mediana a cinci elemente din T. In
consecinta, pentru fiecare i, astfel incat S[i]  m,
exista i₁, i₂, i₃ intre
5i-4 si 5i, astfel ca

T[i₁]  T[i₂]  T[i₃] = S[i]  m

Deci,

#{i  {1, , n} | T[i]  m}  3s/2 = 3n/5/2

= 3(n-4)/5/2 = 3(n-4)/10  (3n-12)/10

Similar, din relatia

#{i  {1, , s} | S[i] < m} < s/2

care este echivalenta cu

#{i  {1, , s} | S[i]  m} > s/2

deducem

#{i  {1, , n} | T[i]  m} > 3n/5/2

= 3n/10 = 3(n-9)/10  (3n-27)/10

Deci,

#{i  {1, , n} | T[i] < m} < (7n+27)/10

In concluzie, m aproximeaza mediana lui T, fiind al k-lea
cel mai mic element al lui T, unde k este aproximativ intre 3n/10
si 7n/10. O interpretare grafica ne va ajuta sa intelegem mai bine aceste
relatii. Sa ne imaginam elementele lui T dispuse pe cinci linii, cu posibila
exceptie a cel mult patru elemente (Figura 7.1). Presupunem ca fiecare din cele
n/5 coloane este
ordonata nedescrescator, de sus in jos. De asemenea, presupunem ca linia din
mijloc (corespunzatoare tabloului S din algoritm) este ordonata nedescrescator,
de la stanga la dreapta. Elementul subliniat corespunde atunci medianei lui
S, deci lui m. Elementele din interiorul dreptunghiului sunt mai
mici sau egale cu m. Dreptunghiul contine aproximativ 3/5 din jumatatea
elementelor lui T, deci in jur de 3n/10 elemente.

Presupunand ca
folosim p  pseudomed(T), adica pivotul este pseudomediana,
fie t(n) timpul necesar algoritmului selection,
in cazul cel mai nefavorabil, pentru a gasi al k-lea cel mai mic element al unui tablou de n elemente. Din inegalitatile

#{i  {1, , n} | T[i]  m}  (3n-12)/10

#{i  {1, , n} | T[i] < m} < (7n+27)/10

rezulta ca, pentru n suficient de mare, tablourile U
si V au cel mult 3n/4 elemente fiecare. Deducem relatia

t(n)  O(n) + t(n/5) + max{t(i) | i  3n/4}
(*)

Vom arata ca t  Q(n). Sa consideram functia
f : N  R^*, definita prin recurenta

f(n) = f(n/5) + f(3n/4) + n

pentru n  N. Prin inductie
constructiva, putem demonstra ca exista constanta reala pozitiva a astfel
incat f(n)  an pentru
orice n  N. Deci, f  O(n).
Pe de alta parte, exista constanta reala pozitiva c, astfel incat t(n)  cf(n)
pentru orice n  N⁺.
Este adevarata atunci si relatia t  O(n).
Deoarece orice algoritm care rezolva problema selectiei are timpul de executie
in W(n), rezulta t  W(n),
deci, t  Q(n).

Generalizand, vom incerca sa aproximam mediana nu numai prin impartire la cinci,
ci prin impartire la un intreg q oarecare, 1 < q  n.
Din nou, pentru n suficient de mare, tablourile U si V
au cel mult 3n/4 elemente fiecare. Relatia (*) devine

t(n)  O(n) + t(n/q) + max{t(i) | i  3n/4}
(**)

Daca 1/q + 3/4 < 1,
adica daca numarul de elemente asupra carora opereaza cele doua apeluri
recursive din (**) este in scadere, deducem, intr-un mod similar cu
situatia cand q = 5, ca
timpul este tot liniar. Deoarece pentru orice q  5
inegalitatea precedenta este verificata, ramane deschisa problema alegerii unui
q pentru care sa obtinem o constanta
multiplicativa cat mai mica.

In particular, putem determina mediana unui
tablou in timp liniar, atat pentru cazul mediu cat si pentru cazul cel mai
nefavorabil. Fata de algoritmul naiv, al carui timp este in ordinul lui n log n, imbunatatirea este substantiala.

clear=all>

Pagini: 1 2 3 4 5 6 7 8 9 10