Relatieve complexiteit

michelhubert · Bericht door **michelhubert** » 02 nov 2012, 16:05

Ik heb twee verschillende ontwerpen voor een softwaresysteem.
En volgens een formule voor complexiteit van Roger Sessions http://www.objectwatch.com/ de onderstaande vergelijkingsformule bedacht.

$R = \frac{ n(x^3 + y^3) + 2(w^3 + v^3)}{ 2( (x+w)^3 + (y+m)^3 ) }$

Boven de deling is de complexiteit van systeem 1 en onder de streep van systeem 2.

Bovendien geldt dat het allemaal natuurlijke getallen zijn die groter zijn dan 0;
$n,x,y,w,v \in \mathbb{N} > 0$ en representeren het aantal functies en afhankelijkheden.

Kan je bewijzen dat altijd geldt: $R > 1$ ?

M.a.w. dat systeem 1 altijd complexer is dan systeem 2 ?

Bericht door **David** » 02 nov 2012, 16:27

Nee. Probeer eens $n = w = x = y = z = 1 \in \mathbb{N}$ .

michelhubert · Bericht door **michelhubert** » 02 nov 2012, 17:57

Ach, dat is wel erg onzorgvuldig van me.

Er zat zelfs nog een fout in de formule;

$R = \frac{ n(x^3 + y^3) + 2(w^3 + v^3)}{ 2( (x+w)^3 + v^3 ) }$

En als $n > 1$ en geldt dan wel $R \geq 1$ ?

Bericht door **arie** » 02 nov 2012, 18:27

$R = \frac{ n(x^3 + y^3) + 2(w^3 + v^3)}{ 2( (x+w)^3 + v^3 ) }$

$= \frac{ n(x^3 + y^3) + 2(w^3 + v^3)}{ 2(x^3+3x^2w+3xw^2+w^3 + v^3 ) }$

$= \frac{ n(x^3 + y^3) + 2(w^3 + v^3)}{ 2(x^3+3x^2w+3xw^2)+ 2(w^3 + v^3 ) }$

Er geldt dus R < 1 als:

$n(x^3 + y^3) + 2(w^3 + v^3) < 2(x^3+3x^2w+3xw^2)+ 2(w^3 + v^3 )$

ofwel

$n(x^3 + y^3)< 2(x^3+3x^2w+3xw^2)$

Stel n=2, x=1, y=1, kan je dan een waarde voor w vinden waarvoor dit geldt?

michelhubert · Bericht door **michelhubert** » 12 nov 2012, 14:11

Bedankt voor je reactie.

Ik heb mijn formule nogmaals herzien tot;
$R = \frac{n(x^3+(2y)^3) + 2(w^3 + (ny)^3)}{2((x+w)^3+y^3)}$

1) Hoe moet je eigenlijk te werk gaan als je wilt uitzoeken hoe de variablene n,x,y en w bijdragen aan een uitkomst > 1?

2) Tevens heb ik geprobeerd om de formule te herschrijven tot 'n=?'. Maar ik blijft ergens steken. Hoe kan ik verder?
$n(x^3+(2y)^3) + 2(w^3 + (ny)^3) = 2R((x+w)^3+y^3)$
$nx^3+n(2y)^3 + 2w^3 + 2(ny)^3 = 2R((x+w)^3+y^3)$
$nx^3+n(2y)^3 + 2(ny)^3 = 2R((x+w)^3+y^3) - 2w^3$
$nx^3+n8y^3 + 2n^3y^3 = 2R((x+w)^3+y^3) - 2w^3$
$n(x^3+8y^3 + 2n^2y^3) = 2R((x+w)^3+y^3) - 2w^3$
maar verder kom ik nog niet.

Wiskundeforum

Relatieve complexiteit

Relatieve complexiteit

Re: Relatieve complexiteit

Re: Relatieve complexiteit

Re: Relatieve complexiteit

Re: Relatieve complexiteit