Springen naar inhoud

Hoe de complexiteit van een algoritme bepalen?



  • Log in om te kunnen reageren

#1

Kwintendr

    Kwintendr


  • >250 berichten
  • 768 berichten
  • VIP

Geplaatst op 15 januari 2013 - 12:22

Hallo iedereen,

De naam van het topic zegt het zelf al, hoe de complexiteit van een algoritme bepalen? In onze cursus informatica staat daar bijna niets over en wat er staat is niet duidelijk ( vind ik toch). Ik ben er al uit wat de complexiteit van een algoritme is. Hoe groter de complexiteit, hoe langer het rekenwerk duurt en bij een log-verband zal de complexiteit minder snel toenemen dan bij een kwadratisch verband. Het probleem is natuurlijk het bepalen van de complexiteit van een algoritme. Na wat lezen op wikipedia kwam ik er op uit dat onze notatie met die O(N) de bovengrens is. Over de ondergrens wordt in de cursus niet gesproken. We zullen dus waarschijnlijk alleen de bovengrens moeten bepalen. Maar ook op wikipedia staat niet hoe je dit moet doen. Kan iemand me helpen?
Het Wetenschapsforum heeft ook een facebook pagina!

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

#2

Xenion

    Xenion


  • >1k berichten
  • 2606 berichten
  • Moderator

Geplaatst op 15 januari 2013 - 12:35

De tijdscomplexiteit wordt bepaald door loops. Je moet zien hoelang je loops duren in functie van de input.

Stel dat ik een loopje heb:
for(i = 0; i < N; i++){ hier code }
Die loop wordt N keer uitgevoerd. Als N verdubbelt dan verdubbelt ook het aantal herhalingen. Dit is O(N).

Een andere:
for(i = 1; i < N; i = i*2){ hier code }
Stel dat N = 4, dan wordt de loop uitgevoerd voor i = 1,2
Als ik nu N verdubbel: N = 8, dan wordt de loop uitgevoerd voor i = 1,2,4
De input is dubbel zo lang, maar het duurt niet dubbel zo lang om de code uit te voeren. Er is immers slechts 1 extra iteratie.

Hier vind je enkele voorbeeld oefeningen en hun oplossing (secties 1.5 en 1.6 respectievelijk).
Je kan er vast nog wel vinden als je eens googlet op big-o exercises, time complexity exercises en variaties daarop.

Veranderd door Xenion, 15 januari 2013 - 12:52
url vergeten toe te voegen


#3

Kwintendr

    Kwintendr


  • >250 berichten
  • 768 berichten
  • VIP

Geplaatst op 15 januari 2013 - 12:42

Maar stel nu dat het aantal bewerkingen van een algoritme 4N+N2+log2N is en je moet bepalen tot welke klasse ze behoren. Dan zou ik denken dat dit een kwadratisch verband is aangezien N2 het grootste effect zal hebben. Maar hoe bepaal je hieruit dan O(f(N))?
Het Wetenschapsforum heeft ook een facebook pagina!

#4

Xenion

    Xenion


  • >1k berichten
  • 2606 berichten
  • Moderator

Geplaatst op 15 januari 2013 - 12:54

Je moet inderdaad naar de dominante term kijken. Het zal dan O(N²) worden.

Ik was de link vergeten toe te voegen aan het woord 'hier' in mijn vorige post.
Bij deze heb ik dat even aangepast :)

#5

Kwintendr

    Kwintendr


  • >250 berichten
  • 768 berichten
  • VIP

Geplaatst op 15 januari 2013 - 13:33

Leuke link, ik heb juist wel 1 vraagje, waarom is dit waar?

5n + 8n2 + 100n3 = O(n4) ik zou eerder zeggen: O(n3)

Zo een vraag vond ik bijvoorbeeld ook niet:

Bepaal de complexiteit van selection sort. Ik weet wat selection sort is, maar hoe moet je daar nu in godsnaam de complexiteit uithalen?
Het Wetenschapsforum heeft ook een facebook pagina!

#6

Xenion

    Xenion


  • >1k berichten
  • 2606 berichten
  • Moderator

Geplaatst op 15 januari 2013 - 13:49

Leuke link, ik heb juist wel 1 vraagje, waarom is dit waar?
5n + 8n2 + 100n3 = O(n4) ik zou eerder zeggen: O(n3)

Dat volgt uit de definitie:
f(n) is O(g(n))
alleen en alleen maar als je een M en x0 kan vinden waarvoor |f(x)| < M |g(x)| voor alle x > x0 (bron)

De uitspraak dat die functie O(n4) is, is juist (want x4 > x3) maar zoals je zelf aangeeft kan je de bovengrens nog 'strakker' maken door O(n3) te noteren.

Bepaal de complexiteit van selection sort. Ik weet wat selection sort is, maar hoe moet je daar nu in godsnaam de complexiteit uithalen?

Hetzelfde als in mijn eenvoudigere voorbeelden: kijk naar de loops die erin gemaakt worden. Hier wordt het uitgelegd voor die specifieke sort.

#7

Kwintendr

    Kwintendr


  • >250 berichten
  • 768 berichten
  • VIP

Geplaatst op 15 januari 2013 - 14:01

De uitspraak dat die functie O(n4) is, is juist (want x4 > x3) maar zoals je zelf aangeeft kan je de bovengrens nog 'strakker' maken door O(n3) te noteren.


Oke, dat is logisch dan

Ik denk dat ik nu ook ongeveer weet hoe ik de complexiteit kan berekenen voor een algoritme. Gewoon nog een kwestie van oefeningetjes te maken om er routine in te krijgen en nog wat meer inzicht :) Bedankt!
Het Wetenschapsforum heeft ook een facebook pagina!

#8

Xenion

    Xenion


  • >1k berichten
  • 2606 berichten
  • Moderator

Geplaatst op 15 januari 2013 - 14:12

Succes ermee :)

#9

Kwintendr

    Kwintendr


  • >250 berichten
  • 768 berichten
  • VIP

Geplaatst op 17 januari 2013 - 22:04

Ik rakel dit onderwerp nog even op omdat ik met iemand aan het discussiëren was. We snappen perfect hoe je aan een complexiteit van n of n^2 of n^3 enz, maar hoe kom je aan een complexiteit van een log of een i^x?
Het Wetenschapsforum heeft ook een facebook pagina!

#10

Xenion

    Xenion


  • >1k berichten
  • 2606 berichten
  • Moderator

Geplaatst op 17 januari 2013 - 22:23

Een andere:
for(i = 1; i < N; i = i*2){ hier code }
Stel dat N = 4, dan wordt de loop uitgevoerd voor i = 1,2
Als ik nu N verdubbel: N = 8, dan wordt de loop uitgevoerd voor i = 1,2,4
De input is dubbel zo lang, maar het duurt niet dubbel zo lang om de code uit te voeren. Er is immers slechts 1 extra iteratie.

Wat is de complexiteit hier?

Een andere: stel ik heb een paswoord van N karakters. Het alfabet van de karakters heeft een grootte L. Hoeveel mogelijke combinaties moet jij in het slechtste geval uittesten om mijn paswoord te kraken?

#11

Kwintendr

    Kwintendr


  • >250 berichten
  • 768 berichten
  • VIP

Geplaatst op 17 januari 2013 - 22:52

Hmm, dat had ik dan verkeerd begrepen. In het eerste geval is het de log omdat je minder bewerkingen moet doen dan dat er N' en bijkomen. Bij het 2de is het dan exponentieel want voor elke N heb je L mogelijkheden -> N^L mogelijkheden.
Ik dacht dat je alleen naar de lops moest kijken, bv 1 loop is complexiteit N, 2 loops is complexiteit N^2, enz . Maar dat is dus duidelijk fout! Bedankt!
Het Wetenschapsforum heeft ook een facebook pagina!

#12

Xenion

    Xenion


  • >1k berichten
  • 2606 berichten
  • Moderator

Geplaatst op 20 januari 2013 - 13:47

Ik had je reactie niet meer gezien, maar ik denk wel dat je het begrijpt. Juist nog 1 detail, maar dat is misschien gewoon een typfout :)

Bij het 2de is het dan exponentieel want voor elke N heb je L mogelijkheden -> N^L mogelijkheden.

Het is L^N mogelijkheden: voor elk van de N karakters heb je L mogelijkheden, dus L*L*...*L (N keer)

Als het N^L was, dan is het niet exponentieel in N, maar gewoon polynomiaal.






Also tagged with one or more of these keywords: informatica

0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures