[informatica] Hoe de complexiteit van een algoritme bepalen?

Kwintendr

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?

Xenion

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.

Kwintendr

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

Xenion

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

Kwintendr

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

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

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?

Xenion

Kwintendr schreef: ↑di 15 jan 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(n³)

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(n⁴) is, is juist (want x⁴ > x³) maar zoals je zelf aangeeft kan je de bovengrens nog 'strakker' maken door O(n³) te noteren.

Kwintendr schreef: ↑di 15 jan 2013, 13:33
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.

Kwintendr

Xenion schreef: ↑di 15 jan 2013, 13:49
De uitspraak dat die functie O(n⁴) is, is juist (want x⁴ > x³) maar zoals je zelf aangeeft kan je de bovengrens nog 'strakker' maken door O(n³) 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!

Xenion

Succes ermee

Kwintendr

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?

Xenion

Xenion schreef: ↑di 15 jan 2013, 12:35
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?

Kwintendr

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!

Xenion

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

Kwintendr schreef: ↑do 17 jan 2013, 22:52
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.

Wetenschapsforum

Laatste berichten

Nieuwsberichten

[informatica] Hoe de complexiteit van een algoritme bepalen?

Hoe de complexiteit van een algoritme bepalen?

Re: Hoe de complexiteit van een algoritme bepalen?

Re: Hoe de complexiteit van een algoritme bepalen?

Re: Hoe de complexiteit van een algoritme bepalen?

Re: Hoe de complexiteit van een algoritme bepalen?

Re: Hoe de complexiteit van een algoritme bepalen?

Re: Hoe de complexiteit van een algoritme bepalen?

Re: Hoe de complexiteit van een algoritme bepalen?

Re: Hoe de complexiteit van een algoritme bepalen?

Re: Hoe de complexiteit van een algoritme bepalen?

Re: Hoe de complexiteit van een algoritme bepalen?

Re: Hoe de complexiteit van een algoritme bepalen?