Page 1 of 1
[AenC] Logaritmische complexiteit.
Posted: Sat Jun 13, 2009 2:36 pm
by Fristi
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
Posted: Sat Jun 13, 2009 2:56 pm
by PieterK
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.
Posted: Sun Jun 14, 2009 10:48 am
by racekakje
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)
Posted: Sun Jun 14, 2009 11:13 am
by Pieter Belmans
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.
Posted: Sun Jun 14, 2009 12:14 pm
by racekakje
Dus eigenlijk heeft elk register een variabele grootte, net zo groot om het getal dat erin zit te bevatten..
Re: [AenC] Logaritmische complexiteit.
Posted: Tue Jun 14, 2011 2:42 am
by djgl3nn
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 ?
Re: [AenC] Logaritmische complexiteit.
Posted: Fri Jun 24, 2011 6:47 pm
by Math Wolf
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?
 = log(n^n) \neq log(n!))
maar wel van dezelfde grootte-orde. (dacht ik toch?)
Re: [AenC] Logaritmische complexiteit.
Posted: Fri Jun 24, 2011 8:14 pm
by djgl3nn
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
