Algoritmen I (2009-2010)

reeks 8: grootste element(en) zoeken

Grootste element

Schrijf een algoritme dat het grootste element in een collectie zoekt op recursieve wijze, door telkens de collectie in twee (ongeveer) gelijke delen te verdelen.

Wat is de performantie van dit algoritme? Is dit beter of slechter dan de triviale manier (een voor een onderzoeken en grootste bijhouden)?

Opm. je kunt het aantal operaties nagaan met FakeInt.

Twee grootste elementen

Er bestaat een interessante manier om de twee grootste elementen uit een collectie te zoeken (onderstel voor de eenvoud dat er geen duplicaten zijn).
De methode is gelijkaardig aan hierboven, maar elke recursieve functie-oproep geeft nu ook een "pool" elementen terug, die kandidaat zijn voor het tweede-grootste element (bevat dus niet het grootste). Na de recursieve oproepen van linker- en rechterdeeltabel moet er slechts 1 van beide pools behouden worden, met daaraan toegevoegd het kleinste van het linker- en het rechtermaximum.

Stel bv. dat de linkertabel een maximum gelijk aan 30 heeft en een kandidatenpool {10, 15, 20}, en dat de rechtertabel een maximum gelijk aan 40 heeft en een kandidatenpool {12, 18}. Het grootste van de twee is duidelijk 40 (rechts). Vermits we zeker weten dat 30 (links) groter is dan de linkerkandidaten (zelfs zonder deze te inspecteren!!), kunnen we die linkerpool weggooien. We houden dus enkel de rechterpool over, en voegen daar het element 30 bij : {12, 18, 30} (ook weer zonder die pool te bekijken!).

Op het hoogste niveau (de oospronkelijke functie-oproep) krijg je uiteindelijk een pool die maximaal O(log(N)) groot is (waarom??). Hiervan kun je het maximum (dus het tweede-grootste element) op een klassieke manier bepalen. Wat is de uiteindelijke performantie??

Maak een implementatie en test uit.