🚀 go-pugleaf

Hello,

> > Andy Georges heeft gelijk, zoeken in een niet-gesorteerde rij is altijd
> > O(n)... Waarom wil je per se recursief werken?
> 
> Because my algorithm would require less comparisons...

daar ga ik niet mee akkoord.

eerst en vooral is het zoeken van de twee grootste eigenlijk hetzelfde
als het zoeken van de grootste, met in elke stap nog een extra
vergelijking om te zien of het nieuwe getal groter is dan het tweede
grootste in het geval het niet het nieuwe grootste is:

if(rij[i] > grootste) {
  groot = grootste; 
  grooste = rij[i];
}
else if(rij[i] > groot) 
  groot = rij[i];

we kunnen dus zeggen dat we eigenlijk het grootste moeten bepalen. 

een iteratief lineair algoritme gebruikt in wezen n-1 vergelijkingen:

grootste = rij[0];
for(int i = 1; i < rij.length; ++i)
  if(rij[i] > grootste)
    grootste = rij[i];

een recursief algoritme dat de rij in twee splitst (laten we voor de
eenvoud veronderstellen dat de lengte van de rij een macht van 2 is)
heeft de volgende kost:

C(N) = C(2^k) = 2 * C(2^{k-1}) + 1

we moeten immers de grootste bepalen uit de twee deelrijen en dan nog
eens vergelijken (merk op dat als we de twee grootste moeten hebben dan
die '1' gewoon een '2' wordt)

en:

C(1) = 0
C(2) = 1

dus:

C(2^k) = 2^m * C(2^{k-m}) + 2^m - 1 (uit de meetkundige rij met factor
2)

dus voor m == k hebben we:

C(2^k) = 2^k * 0 + 2^k - 1 = 2^k - 1 = N - 1

dus in wezen evenveel vergelijkingen als het lineair iteratief
algoritme, maar in de recursieve versie hebben we nog de functieoproepen
waarmee rekening moet worden gehouden.

ik denk dat deze redenering sluitend is, maar opmerkingen zijn
natuurlijk welkom. in elk geval is de recursie ook O(N) wat toch het
belangrijkste is.

mvg,
andy

-- 
==========================================================================
Dept. of Applied Mathematics and Computer Science, University of Ghent
Krijgslaan 281 - S9, B - 9000 Ghent, Belgium
Phone: +32-9-264.47.66, Fax: +32-9-264.49.95
E-mail: andy.georges@rug.ac.be 
==========================================================================