Springen naar inhoud

aantal bewerkingen


  • Log in om te kunnen reageren

#1

Jekke

    Jekke


  • >250 berichten
  • 997 berichten
  • Ervaren gebruiker

Geplaatst op 25 augustus 2006 - 17:33

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.

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

*_gast_PeterPan_*

  • Gast

Geplaatst op 25 augustus 2006 - 21:20

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.

#3

Jekke

    Jekke


  • >250 berichten
  • 997 berichten
  • Ervaren gebruiker

Geplaatst op 26 augustus 2006 - 00:22

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)?)

#4

*_gast_PeterPan_*

  • Gast

Geplaatst op 26 augustus 2006 - 17:10

Correct

#5

Jekke

    Jekke


  • >250 berichten
  • 997 berichten
  • Ervaren gebruiker

Geplaatst op 26 augustus 2006 - 19:19

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.

#6

A.Square

    A.Square


  • >250 berichten
  • 251 berichten
  • Ervaren gebruiker

Geplaatst op 26 augustus 2006 - 22:25

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.





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures