Inleiding
algoritme: eindige reeks instructies die vanuit een gegeven begintoestand naar een beoogd doel
leidt.
Complexiteit van algoritmes
- tijdscomplexiteit: hoe lang duurt het om het probleem op te lossen
- ruimtecomplexiteit: hoeveel geheugen is er nodig om het probleem op te lossen
- hoe hard groeit de tijdsduur naarmate het probleem groter wordt
Algoritmes zijn in te delen in verschillende klassen van complexiteit
voorwaarden van een algoritme:
* volgordelijkheid
* ondubbelzinnig
* uit te rekenen
* eindig
Linear en binair zoeken
lineair zoeken: begint bij het eerste element in een lijst en bekijkt elk
volgend element totdat het gezochte element gevonden is.
binair zoeken: zoeken door het continu halveren van een bepaalde lijst
Lineair zoeken zal veel langer duren dan binair zoeken. Hoe meer
elementen er zijn waartussen je kunt kiezen, hoe groter het verschil tussen
lineair en binair zoeken wordt.
Binair zoeken halveert bij elke keer dat je raadt het aantal uitkomsten. Bij
een lijst van 8 elementen zul je maar hoogstens 4 keer hoeven te raden om
tot het goede antwoord te komen, bij een lijst van 16 element zul je
hoogstens 5 keer moeten raden. Elke keer dat het aantal elementen
verdubbeld, heb je één extra keer raden nodig.
Bij een lijst van lengte n heb je m keer nodig om te raden. Bij een lijst van
lengte 2n heb je m + 1 keer nodig.
Voor deze berekening is er een wiskundige functie: log2n
Dit maakt het makkelijk om het aantal “guesses” bij binair zoeken te
berekenen, als n 128 is, heb je (log2 128 + 1) = 8 guesses nodig.
Als n geen macht van 2 is, kijk je naar de laagste macht van 2 die het
dichtstbij het getal zit.
E.g.
Bij het getal 2,539,913 is de laagste macht van 2 die het dichtbij het getal
is 2^21 ( dat is 2,097,152) dus we hebben hoogstens 22 guesses.
pseudocode: een compromis tussen natuurlijk taal en programmeertaal
Jet Wardenier
algoritme: eindige reeks instructies die vanuit een gegeven begintoestand naar een beoogd doel
leidt.
Complexiteit van algoritmes
- tijdscomplexiteit: hoe lang duurt het om het probleem op te lossen
- ruimtecomplexiteit: hoeveel geheugen is er nodig om het probleem op te lossen
- hoe hard groeit de tijdsduur naarmate het probleem groter wordt
Algoritmes zijn in te delen in verschillende klassen van complexiteit
voorwaarden van een algoritme:
* volgordelijkheid
* ondubbelzinnig
* uit te rekenen
* eindig
Linear en binair zoeken
lineair zoeken: begint bij het eerste element in een lijst en bekijkt elk
volgend element totdat het gezochte element gevonden is.
binair zoeken: zoeken door het continu halveren van een bepaalde lijst
Lineair zoeken zal veel langer duren dan binair zoeken. Hoe meer
elementen er zijn waartussen je kunt kiezen, hoe groter het verschil tussen
lineair en binair zoeken wordt.
Binair zoeken halveert bij elke keer dat je raadt het aantal uitkomsten. Bij
een lijst van 8 elementen zul je maar hoogstens 4 keer hoeven te raden om
tot het goede antwoord te komen, bij een lijst van 16 element zul je
hoogstens 5 keer moeten raden. Elke keer dat het aantal elementen
verdubbeld, heb je één extra keer raden nodig.
Bij een lijst van lengte n heb je m keer nodig om te raden. Bij een lijst van
lengte 2n heb je m + 1 keer nodig.
Voor deze berekening is er een wiskundige functie: log2n
Dit maakt het makkelijk om het aantal “guesses” bij binair zoeken te
berekenen, als n 128 is, heb je (log2 128 + 1) = 8 guesses nodig.
Als n geen macht van 2 is, kijk je naar de laagste macht van 2 die het
dichtstbij het getal zit.
E.g.
Bij het getal 2,539,913 is de laagste macht van 2 die het dichtbij het getal
is 2^21 ( dat is 2,097,152) dus we hebben hoogstens 22 guesses.
pseudocode: een compromis tussen natuurlijk taal en programmeertaal
Jet Wardenier
