🚀 go-pugleaf

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

hiermee ga je toch akkoord, ja?

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

inderdaad. Stel dat we n getallen hebben, ongesorteerd in een bvb array
en we wensen er de N grootste van te bepalen, dan kun je bvb de eerste N
nemen en dan systematisch getallen tussenvoegen als die tussen de
grootste van die N en de kleinste ervan liggen (de kleinste vallen er dan
telkens uit) ik beweer niet dat dit voor grote N het meest efficiente is,
maar voor N << n heb je dus O(N*n) vergelijkingen en afhankelijk van de
implementatie nog wat assignaties (als we de grootste in een gelinkte
lijst bijhouden komt het erop neer dat we 1 assignatie verrichten om het
nieuwe getal in de plaats van de kleinste te knallen en dan nog wat links
verleggen). 

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

neen hoor, quicksort is O(n*log n) stel dus dat N <= log n dan is het
even goed om de hierboven beschreven werkwijze te volgen. als nu 
N > log n , dan kunnen we beter de rij gaan sorteren en dan de N eerste
of N laatste (afh. van de sortering) gaan nemen.

> Dit IS al terug een algoritme dat je naar voor schuift. 

heu, dat was toch de bedoeling he, als je iets verbeterd, moet je ook
zeggen hoe dat kan, dacht ik toch.

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

als je er slechts twee zoekt is het onnodig de hele boel te gaan
sorteren. natuurlijk, mocht je er later bvb drie nodig hebben en dan nog
wat later ook de eerste vijf etc, dan kun je beter direct sorteren, maar
hier ging het om een eenmalige bepaling van de twee grootste getallen uit
een ongesorteerde rij.

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

dat is de idee ja ;-)

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.


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

> 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).

maar 3n/2 is nog steeds O(n) he. en je moet hier ook rekening houden met
de functie-oproepen.

> Btw. het is niet omdat een algoritme gebaseerd is op een recursie-
> betrekking dat je het moet implementeren met behulp van recursieve
> functiecalls. 

neen, maar dan schrijf je het beter direct iteratief op he. of ga jij
even de torens van hanoi, wat je elegant recursief kunt oplossen gaan
implementeren op iteratieve wijze?

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

> Mooi toch, die informatica.

idd.

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