Summary
Samenvatting Algoritmiek
- Course
- Institution
Samenvatting over het onderdeel Algoritmiek van de cursus Analytical Skills gegeven op de HU. Bevat complexiteiten van algoritmes, lineair en binair zoeken en sorteer mechanismen.
[Show more]
1 review
By: mohammedelouali • 3 year ago
Seller
Followjetwardenier
Reviews received
Content preview
Inleidingalgoritme: 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
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller jetwardenier. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $3.79. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
62890 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now