Algoritm pentru minim si maxim

[Phorkias]

Am dat recent o verificare la algoritmica si mi-a dat un subiect care aparent e banal de te doare capu': sa gasesti minimu si maximu intr-un sir. Faza e ca se cerea complexitatea minima si profu chiar a fost cu gluma ca e 3n/2. Eu n-am stiut sa-l fac...

Are cineva vreo idee cam cum suna algoritmul???

[iLogiK]

eu il stiu ceva in genul asta:

Code: Select all

int max=-MAXINT, min=MAXINT
for (int i=0;i<n;i++)
{
    if (A[i]<min) min=A[i];
    if (A[i]>max) max=A[i];
}

MAXINT e constanta pentru cel mai mare numar din domeniul int. Nu sunt sigur daca e MAXINT, sau altcumva, dar ceva in genul asta.
Ideea e ca minimul se initializeaza cu cel mai mare numar posbil, si maximul cu cel mai mic.

[Black Shark]

asta stim cu totii cred, dar intr-un sir neordonat, cu elemente aleatorii chiar nu stiu cum se poate face cautarea altfel...
o mica optimizare la ce a postat Lord ar fi initializarea ambelor variabile cu primul element din sir, verificarile incep de la al doilea, iar verificarea de maxim se pune pe ramura else a verificarii de minim

[Constantin]

Nu e nici o smecherie, ....
Algoritmul are complexitate O(n) .... deci e o simpla parcurgere.

Asta e algoritmul (un fel de pseudocod... spre Java):

Code: Select all

max= a[ 0 ];
min = a[ 0 ];

for (i = 1 ; i < a.length ; i++) do
{
   if ( min > a[ i ] )
   {
      min = a[ i ];
   }
  else 
  if ( max < a[ i ] )
  {
     max = a[ i ];
  }
}

Complexitate O(n) !

Daca este nevoie ca numarul de comparatii sa fie 3n/2 :
http://www.geocities.com/SiliconValley/ ... _minm.html

(desi chiar si ei recunosc ca varianta cu 2n comparatii e muuuult mai rapida.... pt ca e si mai simpla? )

[Black Shark]

constantin, pai asta e algoritmul binecunoscut care se face la inceputul inceputurilor array-urilor in orice liceu(presupun ca si orice alta unitate de invatamant), si exact ce am zis eu in primul post
dar, asta o fi raspunsul la subiectul lui Phorkias ? amplasarea conditiilor si intializarile sunt nedemne de orice fel de testare
---
edit : postul meu corespunde la o varianta usor mai veche(ca numai eu prind situatii din astea) a postului lui Constantin, fara partea finala

[Constantin]

Recunosc,.... partea finala a fost adaugata ...... dupa o documentare pe web... dar oricum ai vazut ca aia recunosc faptul ca dureaza mai mult rularea algoritmului cu numar minim de comparatii ( 3n/2 ) ) ?

[Black Shark]

cam asa se pare, oricum, sunt lucruri utile de stiut, nu ca am face determinarea asta altfel de acum, dar aduce experienta
interesant si site-ul care l-ai link-at, ar merge pus aici

[Phorkias]

Merci pt link. Am aruncat un oki, da mi-ar trebui un dictionar sau ceva sa inteleg si yo pseudocodu la ce-au folosit aia acolo. Da' nu ma las batut...

[SG]

Daca vrei 3n/2, uite un algoritm simplu (nu stiu daca e pe pagina data mai sus):

Pas 1 > ordoneaza perechi consecutive
for i = 0 to n step 2 do
if (vector > vector[i+1]) then
swap(vector, vector[i+1])
endif
endfor

comparatii: n/2

Pas 2 > cauta minim pe pozitiile pare si maxim pe pozitiile impare
min = vector[1]
max = vector[0]
for i = 2 to n step 2 do
if (min > vector) then
min = vector
endif
if (max < vector[i+1]) then
max = vector[i+1]
endif
endfor
return min, max

comparatii: 2*n/2=n

total comparatii: 3n/2
Nu se pun la calcul comparatiile din conditiile for.

Intradevar, timpul total este mai mare, intrucat timpul de scriere este mai mare decat timpul comparatiei, si swap ia o gramada de timp.

[Phorkias]

Algoritmu asta chiar e NICE .

[Phorkias]

Ce mi-a zis un prieten azi: alt algoritm simplu si dragut, si nu vad de ce ar merge greu. Idee e ca compari primele n/2 cu simetricele de la capat si vezi care e max si care e min, care sunt 3 comparatii. Deci ai de cate n/2 ori 3 comparatii = 3n/2. Ma risc sa scriu algoritmu in C:

Code: Select all

if(a[0]>a[n-1]) {max=a[0];min=a[n-1]}
else {max=a[n-1];min=a[0]}
for(i=1;i<n/2+1;i++)
      if(a[i]>a[n-i])
                 {                 
                  if(a[i]>max) max=a[i];
                  if(a[n-i]<min) min=a[n-i];
                  }
       else
                 {                 
                  if(a[n-i]>max) max=a[n-i];
                  if(a[i]<min) min=a[i];
                  }

Sper ca l-am scris bine...