🚀 go-pugleaf

Andy Georges wrote:

> >> 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:
> 
> hiermee ga je toch akkoord, ja?

Nee dus. Dit is 'niet eigenlijk hetzelfde'. Het een is het de
probleemstelling, het andere is een algoritme om dat probleem op te
lossen.
 
> > Wie zegt dat dit
> > het beste algoritme is voor het gegeven probleem, i.e. om de twee
> > grootste getallen te vinden uit een rij ongesorteerde getallen?
> 
> ik :-)

Hoeveel vergelijkingen heeft uw algoritme worst-case dan nodig?

1 + 2*(N-2) tel ik hier gauw (correct me if I'm wrong).

> maar het is tevens zo dat een functie-oproep nog duurder is dan een
> vergelijking. in een imperatieve programmeertaal ga je dit niet zo doen,
> je gaat iteratief te werk.

Jamaar. Ofwel veronderstel je dat een vergelijking peperduur is, oftewel
niet. En bij sorteeralgoritmes geldt als complexiteitsnorm het aantal
vergelijkingen (veronderstel dat je oneindige precisie getallen moet
vergelijken, of strings, of een willekeurige andere orde-relatie ...)

> > Bijvoorbeeld, bedenk als je twee paar getallen hebt (a1 b1) en
> > (a2 b2) waarvoor geldt dat (aX > bX). Hoe vind je nu de grootste
> > twee getallen (a b) van die 4 getallen, opnieuw zodat (a > b)? Dat kan
> > je met twee vergelijkingen doen:
> >
> >   if (a1 > a2) {
> >     a = a1;
> >     if (a2 > b1)
> >       b = a2;
> >     else
> >       b = b1;
> >   }
> >   else {
> >     a = a2;
> >     if (a1 > b2)
> >       b = a1;
> >     else
> >       b = b2;
> >   }
> 
> dit was toch wat ik zei?

Nee. Jij zei:

> 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:

Ik daarentegen zeg:

Het zoeken van de twee grootste kan je doen door de rij in twee te
splitsen,
van die twee deelrijen de twee grootste paren zoeken (a1 b1) en (a2 b2)
en dan is er een combinatie stap met 2 vergelijkingen om de twee
grootste
(a b) van die twee paar twee grootste; met a1 >= b1, a2 >= b2 en a >= b.

Dit kost (voor N een macht van 2) 3/2 * N - 2 vergelijkingen.

Merk op dat ik trouwens minder vergelijkingen doe, dus hoe zouden
we hetzelfde kunnen zeggen?
 
> maar 3n/2 is nog steeds O(n) he. en je moet hier ook rekening houden met
> de functie-oproepen.

Ja, het is nog O(N). Ik heb nooit anders beweerd.

Wat betreft functie-oproepen, nogmaals:
 
> > Btw. het is niet omdat een algoritme gebaseerd is op een recursie-
> > betrekking dat je het moet implementeren met behulp van recursieve
> > functiecalls.

Dus, geen functie calls, maar toch een recursiebetrekking.

> > En dat je ook niet per se hoeft een stack op te bouwen.
> > Bijvoorbeeld de 'staart-recursie' optimizatie die veelal geimplementeerd
> > is in LISP-achtige talen laat een compiler zelfs toe om zelf de
> > stackopbouw eruit te gooien.
> 
> hiet ging het over een imperative taal (Java iirc) en de oorspronkelijke
> oplossing had geen staartrecursie iirc.

Het was dan ook bijvoorbeeld (om aan te tonen dat het zelfs door een
compiler automatisch wordt gedaan; laat staan wat een programmeur zelf
kan doen in java).

koen.