Multidesk.be » Forums » Java » tijdscomplexiteit

  • Pagina
  • 1 van 1
0 gasten lezen dit onderwerp.
^ Onderwerp geschreven door Simon op dinsdag 8 december 2009 om 17:50:37.
Simon's avatar
Multiviteit: 3742
Dit is misschien eerder een algemene programmeervraag maar aangezien wij in Java moeten programmeren stel ik ze in deze categorie.

Het blijkt nu dat wij de tijdscomplexiteit van een stuk code moeten kunnen bepalen. Alleen begrijp ik echt niet hoe men daaraan komt. Een voorbeeld uit de cursus (letterlijk overgenomen), het gaat over een manier om een rij te sorteren via selectie:

CODE
  1. public void selectionSort()
  2. {       //effect: geordend( r[0..r.length-1])
  3.  
  4.         int i,j,positie,maximum;
  5.         int n = r.length;
  6.  
  7.         for( i = n-1; i > 0; i-- )
  8.         {       //geordend (r[i+1..n-1])
  9.                
  10.                 maximum = r[i];
  11.                 positie = i;
  12.                 for( j = i-1; j >= 0; j--)
  13.                 {
  14.                         if( r[j] > maximum)
  15.                         {
  16.                                 maximum = r[j];
  17.                                 positie = j;
  18.                         }
  19.                 }
  20.                
  21.                 r[positie] = r[i];
  22.                 r[i] = maximum;
  23.                 //geordend (r[i..n-1])
  24.                 //en r[i] >= [0..i-1]
  25.         }
  26.         //geordend(r[1..n-1])
  27.         //en r[1] >= r[0]
  28.         // geordend (r[0..n-1])
  29. //
  30. }


Dan staat er dit voor de berekening van complexiteit

Dixit

Complexiteitsanalyse:

  • probleemgroote: n = lengte van de rij

  • meest-tijdrovende bewerkingen tellen:
    • toekenningen van elementen in rij AT
    • vergelijkingen AV

  • verwaarlozing van de andere bewerkingen:
    • verwaarloosbare tijd
    • het asymptotisch gedrag wordt niet be´nvloed



Aantal toekenningen AT:
ATmin = (n-1)*3 (reeds gesorteerde lijst)

ATmax = (n-1)*3 + (n-1)+(n-3)+...+4+2 n oneven
ATmax = (n-1)*3 + (n2-1)/4
ATmax = gelijkaardig voor n even

==> ATmax = (n-1)*3 + n2/4

ATgem = (ATmax +ATmin)/2

==> ATgem = (n-1)*3 + n2/8

De tijdscomplexiteit is O(n2).

Aantal vergelijkingen AV:
onafhankelijk van de elementen in de rij

AV = (n-1)+(n-2)+(n-3)+...+2+1
AV = n*(n-1)/2

De tijdscomplexiteit is O(n2).

==> Totale uitvoeringstijd (AT en AV) is O(n2).

^ Reactie #1 geschreven door thekid op dinsdag 8 december 2009 om 19:02:09.
thekid's avatar
Multiviteit: 5273
Moderator
wat wil je nou net weten? :)
"Human beings make life so interesting. Do you know, that in a universe so full of wonders, they have managed to invent boredom." - Death in Hogfather
^ Reactie #2 geschreven door StOosh op dinsdag 8 december 2009 om 19:04:31.
StOosh's avatar
Multiviteit: 1526

Dixit

Het blijkt nu dat wij de tijdscomplexiteit van een stuk code moeten kunnen bepalen. Alleen begrijp ik echt niet hoe men daaraan komt
Dat wil 'ie weten ;)
Deze tekst werd het laatst bewerkt voor 0.9 % door StOosh op dinsdag 8 december 2009 om 19:04:41.
^ Reactie #3 geschreven door thekid op dinsdag 8 december 2009 om 19:11:27.
thekid's avatar
Multiviteit: 5273
Moderator
vaneigens dadde Stoosh, maar ie heeft alle bewerkingen ervoor (zie zijn extra stuk tekst eronder) dus vraag ik mij af wat ie nog nodig heeft aan extra info.

dus ik vraag mij af, wat ie wel al begrijpt en wat ie beter wil uitgelegd zien ;)
"Human beings make life so interesting. Do you know, that in a universe so full of wonders, they have managed to invent boredom." - Death in Hogfather
^ Reactie #4 geschreven door Simon op dinsdag 8 december 2009 om 22:07:41.
Simon's avatar
Multiviteit: 3742
Sorry, was iets te onduidelijk.

Neem nu bijvoorbeeld ATmin=(n-1)*3. Het ligt voor de hand dat er een minimum aan bewerking uitgevoerd zal worden als de rij al gesorteerd is. Dat begrijp is dus. Maar waar komt (n-1)*3 vandaan?
Ik zie binnen de eerste for-lus slechts 2 toekenningen van elementen in een rij staan (regel 21 en 22) hier. Hoe komt men dan aan maal 3?
En ik begrijp al helemaal niet hoe men dan aan die extra termen komt bij ATmax.

^ Reactie #5 geschreven door NightCreature op woensdag 9 december 2009 om 22:24:16.
NightCreature's avatar
Multiviteit: 1196
MSc.
Tijds complexiteit met loops is heel makkelijk te zien als je twee loops in elkaar hebt die over het hele array loopt weet je al dat je kwadratisch bezig bent.
Zoals ik het geleerd hebt maakt het toekennen en vergelijken van waarden weinig uit wat je doet. Wat je wil tellen is hoe vaak een loop iets doet. En dat iets kan vergelijken, toekenen of meerdere operaties zijn. Dit komt omdat over het algemeen een constante toename zoals de 3 in het voorbeeld er eigenlijk niet toe doet om een lus te laten lopen.

Je vergeet de assginment aan de loop counter daar komt de 3 door. Max komt doordat je de binneste loop ook begint uit te voeren en die loopt van 0 tot de huidige i waarde.

Maar zoals ik al zei omhet makkelijk te houden tel je normaal alleen maar hoevaak een for/while/recursie wordt gedaan.

Een binairy search heeft bevoorbeeld als O(log n) als complexiteit, dit komt omdat je steeds het midden van het array bepaalt en daar vanaf in het eerste deel of laatste deel gaat zoeken. Alle log zijn trouwens base 2 in tijdscomplexiteit een goed boek is trouwens Introduction to algorithms duur boek maar staat meer in dan alleen tijdscomplexiteit

In de werk wereld gebruik je tijdscomplexiteit echter bijna nooit(in ieder geval ik niet), daar kijk je echt veel meer naar "ow ik gebruik hier twee loops in elkaar kan dat ook in een".

By the way the selectionSort van je kan ook met een loop gedaan worden, als ik het goed heb. Zal morgen ff wat code opsnorren uit die een lijst van integers sorteert op aflopend level van de speler en tegelijker tijd ook nog eens op team sorteert.
Deze tekst werd het laatst bewerkt voor 4.34 % door NightCreature op woensdag 9 december 2009 om 22:44:05.
I need thought completion.
Shaders, een beetje vreemd maar wel lekker (voor de ogen dan he)
2.83Ghz Q9550 HD4850 512MiB 4GiB 1333Mhz DDR3 RAM
http://paulintheuk.blogspot.com
FE Programmer @ Codemasters (Front End)
^ Reactie #6 geschreven door Simon op woensdag 9 december 2009 om 23:18:05.
Simon's avatar
Multiviteit: 3742

Dixit

Dixit NightCreature op 09/12/2009 22:24:16:
Je vergeet de assginment aan de loop counter daar komt de 3 door.


Maar dan zijn er toch nog meer toekenningen die ik kan meerekenen? Ik tel er 8. Omdat de prof AT definieerde als "toekenningen van elementen in rij" dacht ik dat je enkel deze moest nemen.

Dixit

Dixit NightCreature op 09/12/2009 22:24:16:
Maar zoals ik al zei omhet makkelijk te houden tel je normaal alleen maar hoevaak een for/while/recursie wordt gedaan.

Dan is het minimum aantal keren dat men door de lus loopt dus n-1. Het maximum aantal keren is dan n-1 + n-1 + n-2 + n-3 + ... + 1. Hoe komt men dan aan het kwadraat? Of zie ik het nu echt helemaal verkeerd?
^ Reactie #7 geschreven door NightCreature op donderdag 10 december 2009 om 01:27:05.
NightCreature's avatar
Multiviteit: 1196
MSc.
Omdat de lussen anders om lopen zal het aantal keer zelfs voor een georderd array (n-2) * (n-1) zijn. i = n-1 in de eerste loop in het begin daardoor is j = n - 2, een dubbele for loop is altijd een * operator. (n-2)*(n-1)=N^2 - 3n + 2, hier uit neem je enkel de n met de hoogste exponent omdat de rest neer komt op een constante factor die je erbij telt.
Maar zelfs al zouden de lussen op omhoog lopen zou je er kwadratisch door heen loop maar dat voorbeeld laat ik aan de lezer over.

miernneukerij:
Een ander punt je zou je toekenning in de for loop als --i en --j moet schrijven dit elimineert namelijk een toekenning en deze functies voor int komen neer op de asm instructie inc eax. Vooral als je operator ++ overload wordt de preincrement sneller in een for loop. preincrement komt namelijk neer op verhogen voor gebruik en post increment is verhogen na gebruik, het scheelt 1 instructie hier maar als de operator overloaded is kan het meer schelen. Het is niet verkeerd echter als je altijd preincrement in een for gebruikt zul je het nooit vergeten te doen.
Deze tekst werd het laatst bewerkt voor 6.26 % door NightCreature op donderdag 10 december 2009 om 01:41:33.
I need thought completion.
Shaders, een beetje vreemd maar wel lekker (voor de ogen dan he)
2.83Ghz Q9550 HD4850 512MiB 4GiB 1333Mhz DDR3 RAM
http://paulintheuk.blogspot.com
FE Programmer @ Codemasters (Front End)
^ Reactie #8 geschreven door Simon op donderdag 10 december 2009 om 19:44:54.
Simon's avatar
Multiviteit: 3742
Ok, ik begin het te snappen. Dit weekend zal ik nog eens enkele voorbeelden uit de cursus bekijken en eens zien of ik daar ook de complexiteit van kan bepalen.

Bedankt voor de tip over die preincrement. Ik zal het zeker in gedachten houden. Bovenstaande code is echter van de prof zelf en heb ik gewoon overgenomen uit de cursus.
^ Reactie #9 geschreven door NightCreature op vrijdag 11 december 2009 om 13:13:10.
NightCreature's avatar
Multiviteit: 1196
MSc.
Die code komt rechtstreeks uit Introduction to Algorithms trouwens want dat is daarin namelijk een opdracht om de tijdscomplexiteit voor te bepalen. Enkel is de psuedo code van het boek omgezet in Java.
I need thought completion.
Shaders, een beetje vreemd maar wel lekker (voor de ogen dan he)
2.83Ghz Q9550 HD4850 512MiB 4GiB 1333Mhz DDR3 RAM
http://paulintheuk.blogspot.com
FE Programmer @ Codemasters (Front End)
^ Reactie #10 geschreven door Simon op dinsdag 5 januari 2010 om 15:11:40.
Simon's avatar
Multiviteit: 3742
Blijkbaar moeten wij dus echt die berekening kunnen maken. Een argument als "er zijn 2 lussen in elkaar, dus de tijdscomplexiteit is kwadratisch" is niet goed genoeg.

Ik heb van bovenstaande code zelf eens proberen de berekening maken en ik kom op het volgende uit:
ATmin = (n-1)*3
ATmax = 3+(n-1)+3+(n-2)+...+3+2+3+1
De 3's komen van de toekenningen in de buitenste lus en de (n-1),(n-2),... komen van de toekenningen in de binnenste lus.
Die 3 toekenningen worden in totaal (n-1) keer uitgevoerd en het andere is de som van een rekenkundige rij die gelijk is aan n*(n-1+1)/2 dus
=(n-1)*3+n^2/2
ATgem = (n-1)*3+n^2/4
Hier kom ik dus 1/4*n^2 uit terwijl de prof daar &/8*n^2 had. Wat doe ik nu precies fout?

AVmin = n-1
AVmax = 1+(n-1)*2+1+(n-2)*2+...+1+2*2+1+1*2
De 1'tjes komen van de vergelijking in de eerste for-lus die n-1 keer gebeurd. En de 2*(n-1),2*(n-2),... komen van de 2 vergelijkingen in de binnenst for-lus.
Als we de 2 afzonderen en opnieuw de formule voor som van een rekenkundige rij toepassen krijgen we:
=n-1+2*n^2/2
=n-1+n^2
En ook hier kom ik een andere waarde uit?

Randinformatie

Een BB-code om LaTeX te kunnen typen zou handig zijn :).

Deze tekst werd het laatst bewerkt voor 3.02 % door Simon op dinsdag 5 januari 2010 om 15:12:15.
^ Reactie #11 geschreven door Simon op zaterdag 9 januari 2010 om 16:24:33.
Simon's avatar
Multiviteit: 3742
Ik had nog een vraag:
CODE
  1. public int fibonnacciRecursief(int n){ if(n==1 || n==2) return 1; else return fibonnacciRecursief(n-2) + fibonnacciRecursief(n-1);
  2. }

Voor deze methode zou de complexiteit blijkbaar 2^n moeten zijn. Hoe komt men daaraan?
  • Pagina
  • 1 van 1

Snel-antwoordformulier
Toon uitgebreid antwoordformulier Bericht nalezen Bericht plaatsen