[AenC] Logaritmische complexiteit.

Forum van 2de Bachelor Informatica.

Moderator: Praesidium

User avatar
Fristi
WOZ
Posts: 4565

[AenC] Logaritmische complexiteit.

Post#1 » Sat Jun 13, 2009 2:36 pm

Loha

Had is een vraagske over complexiteit in het logaritmisch kostcriterium.

Bijvoorbeeld bij reeks4, de eerste oefening. Er staat bereken de plaatscomplexiteit van een de gegeven code.
Ik heb van iemand de uitkomst O(n log(n)), maar hoe komt ge hieraan?

De code waar het om gaat is:

Code: Select all

READ 1
LOAD =1
STORE 2
LOAD =2
STORE 3
test SUB 1
JGTZ end
LOAD 2
MULT 3
STORE 2
LOAD 3
ADD =1
STORE 3
JUMP test
end WRITE 2
HALT
In het unifmrok kostcriterium snap ik dit, maar zou iemand dit kunnen uitleggen voor het logaritmisch?

Alvast bedankt!
Fristi
Fristi Ad Infinitum

WINAK WOZ 2013 - ...
WINAK Magister Fristi 2012-2013
WINAK Feest 2011-2012
WINAK Schachtentemmer 2010-2011
WINAK Scriptor 2008-2009 | 2009-2010

User avatar
PieterK
Posts: 118

Post#2 » Sat Jun 13, 2009 2:56 pm

Ge bepaalt de maximale waarde die in elk van de gebruikte registers gedurende de hele uitvoering van het programma staat. In dit geval gebruikt ge 4 registers: r0, r1, r2, r3. En dan past ge wat er op p19 staat toe. Om u op weg te helpen: de grootste waarde die r0 zal bevatten is n! dus l(r0) = log(n!) + 1. Dit doet ge ook voor de 3 andere registers waarna ge sommeert. Na uitwerking zoud ge inderdaad O(nlog(n)) moete krijgen.

User avatar
racekakje
WOZ
Posts: 740

Post#3 » Sun Jun 14, 2009 10:48 am

Ik snap eigenlijk niet waarom de grootte van de waarde in uw registers er toe doen..

Ik vind dat het lijkt alsof tijdscomplexiteit te maken heeft met de tijd nodig om een programma uit te voeren en plaatscomplexiteit het geheugen dat programma gebruikt.

In die veronderstelling moet je toch het aantal registers die gebruikt worden in rekening houden?

(Ik trek de oplossing van Pieter hier niet in twijfel, want dat is idd het gene de cursus doet. Ik begrijp het gewoon niet)

Pieter Belmans
Posts: 593
Contact:

Post#4 » Sun Jun 14, 2009 11:13 am

Het gaat om operanden van willekeurige grootte. Ge zijt gewend om in integers te denken, maar ge kunt evengoed met bignums werken die zo groot als ge wilt kunnen worden. Operaties en opslag van zo'n getallen is immers niet in O(1) uit te voeren.

User avatar
racekakje
WOZ
Posts: 740

Post#5 » Sun Jun 14, 2009 12:14 pm

Dus eigenlijk heeft elk register een variabele grootte, net zo groot om het getal dat erin zit te bevatten..

User avatar
djgl3nn
WOZ
Posts: 1938

Re: [AenC] Logaritmische complexiteit.

Post#6 » Tue Jun 14, 2011 2:42 am

vermits log(n!) gelijk is aan n log(n)
had ik voor de logaritmische plaatscomplexiteit iets van :
n log(n) + n log(n) + n + n ofzo wat dan 2n log(n) + 2n is , en da dan O( n* log(n) ) wordt ?

Voor de tijdscomplexiteit, was mijn theorie een beetje de plaatscomplexiteit maal die loop. ( die ge n keer door gaat )
n*n*log(n) = n²log(n)

some opinions ?
WINAK Schacht 2009-2010
WINAK Sport 2010-2011
WINAK Mentor Informatica 2011-2012
WINAK Ouwe Zak 2012-...

UA Sportraad Webmaster 2012-...

User avatar
Math Wolf
Posts: 4053
Contact:

Re: [AenC] Logaritmische complexiteit.

Post#7 » Fri Jun 24, 2011 6:47 pm

djgl3nn wrote:log(n!) gelijk is aan n log(n)
whut? Gewoon uit nieuwsgierigheid, ik veronderstel dat je in grootte-orde bedoelt en geen gelijkheid?

maar wel van dezelfde grootte-orde. (dacht ik toch?)
2014: Jan16, Feb15, Mar16, Apr15, May14, Jun13, Jul12, Aug10, Sep9, Oct8, Nov6, Dec6
2015: Jan5, Feb5, Mar5, Apr4, May4, Jun2, Jul2, Jul31, Aug29, Sep28, Oct27, Nov25, Dec25

User avatar
djgl3nn
WOZ
Posts: 1938

Re: [AenC] Logaritmische complexiteit.

Post#8 » Fri Jun 24, 2011 8:14 pm

Math Wolf wrote:
djgl3nn wrote:log(n!) gelijk is aan n log(n)
whut? Gewoon uit nieuwsgierigheid, ik veronderstel dat je in grootte-orde bedoelt en geen gelijkheid?

maar wel van dezelfde grootte-orde. (dacht ik toch?)
jah in Big Oh wel te verstaan :D
WINAK Schacht 2009-2010
WINAK Sport 2010-2011
WINAK Mentor Informatica 2011-2012
WINAK Ouwe Zak 2012-...

UA Sportraad Webmaster 2012-...

Return to “2de Bachelor”

Who is online

Users browsing this forum: No registered users and 5 guests

cron