🚀 go-pugleaf

Andy Georges wrote:
> 
> 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:

En is het zoeken van de drie grootste eigenlijk hetzelfde als het
zoeken van de grootste, met in elke stap twee extra vergelijkingen,
...

En is het zoeken van de N grootste eigenlijk hetzelfde als het
zoeken van de grootste, met in elke stap nog N-1 extra vergelijkingen,
...

Met andere woorden, zijn quicksort en consoorten dus maar fabeltjes?!

Nee dus.

Dit IS al terug een algoritme dat je naar voor schuift. 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?

Tenmiste, als we onder 'beste' het algoritme verstaan met het minst
vergelijkingen, dus onder de veronderstelling dat de vergelijking
peperduur is.

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;
  }

Breid dit uit naar een recursie-betrekking en je vindt dat
het aantal vergelijkingen dus werkelijk minder is dan 2N (ik
vermoed iets van 3N/2).

Btw. het is niet omdat een algoritme gebaseerd is op een recursie-
betrekking dat je het moet implementeren met behulp van recursieve
functiecalls. 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.

Mooi toch, die informatica.

koen.