Case uitwerking
Computational Thinking Assignment 3
- Instelling
- Vrije Universiteit Amsterdam (VU)
Computational Thinking Assignment 3
[Meer zien]Voorbeeld 2 van de 8 pagina's
Voorbeeld 2 van de 8 pagina's
In winkelwagengesponsord bericht van onze partner
Verkoper
Volgen
Voorbeeld van de inhoud
Computational Thinking – Assignment 3 (Artificial Intelligence Year 1)1. Comparison of keys
Keys 4 13 25 33 38 41 55 71 73 84 86 92 97
Index 0 1 2 3 4 5 6 7 8 9 10 11 12
We need to use binary search: worst case performance, because that will lead to the largest
possible number of key comparisons. In this list, we have 13 indices, because we need to start
counting the keys from k = 0. The formula we need to use is ⎡ log2(n + 1) ⎤.
⎡ log2(n + 1) ⎤ = log2 (13 + 1) = 3.80735492206 ≈ 4
Conclusion: when you look up a key with binary search, the largest possible number of key
comparisons in this list is 4.
2. Estimating performance
A.
Binary search
Average case of successful search: ~ log2 (n)
Average case of successful search in a sorted array of 100,000 elements:
~log2 (100,000) = 16.609640474436812 ≈ 16.6
Sequential/linear search
Average case of successful search: (n + 1) / 2
Average case of successful search in a sorted array of 100,000 elements:
(100,000 + 1) / 2 = 50000.5
As you can see the 1 in (n + 1) / 2 is neglectable, because it’s a really small number compared to
100,000. You will get: (100,000) / 2 = 50000.
An average successful search by binary search is .6 ≈ 3010 times faster than an
average successful search by sequential search.
B.
We have a sorted array of 100,000 elements. To draw a single graph for both
linear (= sequential) and binary search, we need to use the “Big O” notation. The big O notation is
used to classify algorithms. It is a function characterization according to rates of growth and it is
useful for analysing efficiency. In this case, we consider worst cases. The worst cases for the
binary and linear search algorithms are:
- Binary = O(log(n))
- Linear = O(n)
I drew a
single graph
in Python as
follows:
, Computational Thinking – Assignment 3 (Artificial Intelligence Year 1)
This is the result I got, after I clicked “run”.
We can see that the number of operations (for 100,000 elements) with the binary search
algorithm, is a lot less than with linear search, if you consider worst case scenario’s. In this case, if
you want to find a key, it is better and way faster to use the binary search algorithm.
3. Binary search in flowchart
This in my flowchart for binary search, made in excel.
Voordelen van het kopen van samenvattingen bij Stuvia op een rij:
Verzekerd van kwaliteit door reviews
Stuvia-klanten hebben meer dan 700.000 samenvattingen beoordeeld. Zo weet je zeker dat je de beste documenten koopt!
Snel en makkelijk kopen
Je betaalt supersnel en eenmalig met iDeal, creditcard of Stuvia-tegoed voor de samenvatting. Zonder lidmaatschap.
Focus op de essentie
Samenvattingen worden geschreven voor en door anderen. Daarom zijn de samenvattingen altijd betrouwbaar en actueel. Zo kom je snel tot de kern!
Veelgestelde vragen
Wat krijg ik als ik dit document koop?
Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.
Tevredenheidsgarantie: hoe werkt dat?
Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.
Van wie koop ik deze samenvatting?
Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper TR19. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €5,49. Je zit daarna nergens aan vast.
Is Stuvia te vertrouwen?
4,6 sterren op Google & Trustpilot (+1000 reviews)
Afgelopen 30 dagen zijn er 83100 samenvattingen verkocht
Opgericht in 2010, al 14 jaar dé plek om samenvattingen te kopen