Laatste berichten
-
00:15
[scheikunde] Kan chloorgas de geleiding van elektriciteit belemmeren? 9
-
22:27
positie 1
-
21:15
Weerfrustratie 9
-
18:24
Schroefdraad berekening 5
-
18:08
geen minkowski-ruimte toch? Doe ik dit nou fout? 15
-
14:16
do-re-mi-fa-so vliegtuigen 7
-
14:16
Kunnen quantum Zonnecellen 190% quantum efficiënt zijn 3
-
13:57
De Euro Nederlandse 100 qubit computer komt eraan
-
10:42
projectiel 8
-
10:37
Verschil tussen deze 2 vragen 5
-
09:25
[scheikunde] berekeningen labo vitamine c bepaling 1
-
22 apr
[wiskunde] rode en witte ballen verdelen 8
-
22 apr
Rotatie van het heelal 41
-
22 apr
Muntje opgooien 14
-
21 apr
Reactiviteit silyl enol ethers 1
-
21 apr
Criterium voor vochtretentie
-
21 apr
speciale rel. theorie 5
-
21 apr
Vogels in de stad zijn goede klussers
-
21 apr
Ervaringen met "herontdekkingen" 15
-
20 apr
Herleiden afmetingen vanaf een foto 19
Nieuwsberichten
-
04 mar
Een nieuw soort magnetisme: altermagnetisme
-
31 okt
AI kan via stem diabetes vaststellen 11
-
21 okt
Einstein krijgt wéér gelijk 45
-
07 feb
witter dan wit 20
-
19 jun
irrigatie en de aardas
aantal bewerkingen
Forumregels
(Middelbare) school-achtige vragen naar het forum "Huiswerk en Practica" a.u.b.
Zie eerst de Huiswerkbijsluiter
(Middelbare) school-achtige vragen naar het forum "Huiswerk en Practica" a.u.b.
Zie eerst de Huiswerkbijsluiter
-
- Berichten: 997
aantal bewerkingen
Hoe kan je inzien hoeveel bewerkingen er nodig zijn om een natuurlijk getal n te reduceren tot 1 of 0 door enkel de bewerkingen "delen door 2" en "min 1" te gebruiken? (Respectievelijk wanneer het deelresultaat even en oneven is.) Of is dit misschien niet mogelijk? Het heeft te maken met de complexiteit van een algoritme.
Re: aantal bewerkingen
Zij n het natuurlijke getal in kwestie.
Schrijf het getal binair.
Dat geeft een getal van a=[1+2log n ] cijfers waarvan er zeg b enen zijn.
Het aantal bewerkingen is dan a + b.
Schrijf het getal binair.
Dat geeft een getal van a=[1+2log n ] cijfers waarvan er zeg b enen zijn.
Het aantal bewerkingen is dan a + b.
-
- Berichten: 997
Re: aantal bewerkingen
Dus als ik een algoritme (een lus) heb dat a+b bewerkingen doet en ik bekijk het ergste geval (het geval met meest aantal bewerkingen) dan zijn er dus 2a bewerkingen. Bijgevolg kan ik zeggen dat de tijdscomplexiteit = O(2a) = O(2(1+²log n )) = O(²log n ) = O(log n ). Klopt dit? (b Kan toch nooit sneller stijgen in functie van n dan a (asymptotisch)?)
-
- Berichten: 997
Re: aantal bewerkingen
Erg bedankt! (Die truc van binair schrijven daar was ik nooit opgekomen.) Overigens wel vreemd dat zulk een algoritme dezelfde complexiteit heeft als een algoritme dat elke keer het min 1 doet ineens ook deelt door 2.
-
- Berichten: 251
Re: aantal bewerkingen
Erg bedankt! (Die truc van binair schrijven daar was ik nooit opgekomen.) Overigens wel vreemd dat zulk een algoritme dezelfde complexiteit heeft als een algoritme dat elke keer het min 1 doet ineens ook deelt door 2.
Daarom is binair rekenen zo mooi. Vermenigvuldigen is 'hetzelfde' als optellen.
En daarom kunnen we een AND-poort gebruiken om bewerkingen te doen.
