Getallen van Fibonacci berekenen.

[jhnbk]

Mooi zo. Nu nog de complexiteit van beide algoritmen vergelijken.

[Rogier]

Ze lijken me ongeveer even complex, beide van orde

\({\cal O}(\log(n))\)

, en een paar optellingen en vermenigvuldigingen per iteratie. In mijn laatste variant van de matrixmethode zitten minder operaties, maar daarentegen gooit de recursie misschien weer wat roet in het eten (een directe loop van N iteraties is efficiënter dan recursie van N niveaus diep).

[Rogier]

Nóg ietsje optimaler dan:

Code: Selecteer alles

static int ma,mb,mc,mt; // {{ma mb}{mb mc}} representeert de matrix, mt is temp



void MatrixPower( int n )

{

	if (n>1)

	{

		MatrixPower(n>>1);



		// M = M * M

		mt = mb*mb;

		mb *= ma+mc;

		ma = ma*ma + mt;

		mc = mc*mc + mt;

	}

	if (n&1)

	{

		// M = M * {{1 1}{1 0}}

		mc = mb;

		mb = ma;

		ma += mc;

	}

}



int Fib( int n )

{

	ma = mc = 1;

	mb = 0;

	MatrixPower(n-1);

	return ma;

}

[jhnbk]

Ze lijken me ongeveer even complex, beide van orde

\({\cal O}(\log(n))\)

, en een paar optellingen en vermenigvuldigingen per iteratie. In mijn laatste variant van de matrixmethode zitten minder operaties, maar daarentegen gooit de recursie misschien weer wat roet in het eten (een directe loop van N iteraties is efficiënter dan recursie van N niveaus diep).

Als ik het goed begrijp kan van de complexiteit niet eenduidig afgeleid worden welk algoritme beter presteert. (Ik zou niet weten hoe ik zelf de complexiteit van ene algoritme kan bepalen. Ken je geen sites/ebooks die dat onderwerp kort behandelen?)

[PeterPan]

Als ik het goed begrijp kan van de complexiteit niet eenduidig afgeleid worden welk algoritme beter presteert. (Ik zou niet weten hoe ik zelf de complexiteit van ene algoritme kan bepalen. Ken je geen sites/ebooks die dat onderwerp kort behandelen?)

De complexiteit zegt iets over hoe goed een programma is voor grote waarden.

Neem de berekening van

\(F_n\)

.

Misschien is het mogelijk een programma te schrijven van orde

\({\cal} O (\exp(n))\)

dat voor

\(n<100\)

beter presteert dan een programma van orde

\({\cal} O (\log(n))\)

.

Het verschil in orde zit hem hier in, dan ik bijvoorbeeld in het programma van orde log(n) de

\(F_n\)

kan bepalen voor

\(n<10.000.000\)

binnen 5 minuten, terwijl in het programma van orde exp(n) de

\(F_n\)

er voor

\(n>200\)

er minimaal 50.000 jaar over doet.

Dit is geen overdreven voorbeeld!

Wat je in eerste instantie altijd wilt is een algoritme met een rekentijd van zo laag mogelijke orde. Vervolgens ga je kijken binnen die verzameling van mogelijke algoritmen welke de snelste is.

Voorbeeld: nxn-Matrices vermenigvuldigen gaat met orde

\({\cal} O (n^3)\)

.

Met het Strassen algoritme met orde

\({\cal} O (n^{2,807})\)

.

Een enorme versnelling.

Echter het Strassen algoritme is pas sneller voor

\(n>31\)

.

Voor

\(n<32\)

is het sneller om de normale matrixvermenigvuldigings manier te gebruiken.

Er zijn algoritmen voor matrixvermeningvuldiging van nog kleinere orde.

Die zijn echter niet bruikbaar, omdat die pas efficient zijn voor matrices die groter zijn dan 500.000x500.000.

Voor de praktisch toepassing te verweg.

[PeterPan]

Als ik het goed begrijp kan van de complexiteit niet eenduidig afgeleid worden welk algoritme beter presteert. (Ik zou niet weten hoe ik zelf de complexiteit van ene algoritme kan bepalen. Ken je geen sites/ebooks die dat onderwerp kort behandelen?)

Om de complexiteit van een algoritme te bepalen moet je kijken naar de loops en recursies.

In het voorgaande algoritme roept (alles bij benadering) MatrixPower(n), MatrixPower (n/2) aan, die zelf weer MatrixPower (n/4) aanroept enz.

Hoeveel werk is dat (afhankelijk van n): Het aantal elementen van de rij n,n/2,n/4,...,1

Als dat aantal k is dan is

\(2^k = n\)

, dus

\(k = c\log(n)\)

voor zekere constante c.

Dus hoeveelheid werk is in orde van grootte van (constante x)

\(\log(n)\)

.

We zeggen dan de complexiteit is

\({\cal} O (\log(n))\)

[Cycloon]

Wat je in eerste instantie altijd wilt is een algoritme met een rekentijd van zo laag mogelijke orde. Vervolgens ga je kijken binnen die verzameling van mogelijke algoritmen welke de snelste is.

Op zich niet echt correct, algoritmen van de beste orde kunnen in bepaalde gevallen véél slechter presteren dan algoritmen die een gemiddelde orde hebben die heel wat slechter is (zoals quicksort die even traag wordt als selection sort). Als je met gegevens gaat werken die net voor die gevallen gaan zorgen moet je weer alle algoritmen gaan herbekijken. Vaak is het kiezen van het "beste" algoritme ook wel een discussie zoals twisten over smaken. Natuurlijk, in 90% van de gevallen zal een algoritme met de beste orde wel zijn werk goed doen.

[PeterPan]

Het is inderdaad wat kort door de bocht; ik had er "in principe" of "in eerste instantie" of iets dergelijks tussen moeten zetten. Zie mijn voorbeeld van matrixvermenigvuldiging. En over smaak gesproken; je kunt ervoor kiezen een algoritme te nemen dat in worst case een rekentijd heeft van orde

\(n^2\)

en van gemiddelde rekentijd

\(O(n\log(n))\)

en dat verkiezen boven een algoritme van orde

\(n\sqrt{n}\)

.

[Vladimir Lenin]

Als ik het goed begrijp kan van de complexiteit niet eenduidig afgeleid worden welk algoritme beter presteert. (Ik zou niet weten hoe ik zelf de complexiteit van ene algoritme kan bepalen. Ken je geen sites/ebooks die dat onderwerp kort behandelen?)

De complexiteit zegt enkel iets over de grootorde van n, niet over hoelang een algoritme duurt, een algoritme van n! kan beter presteren dan bijvoorbeeld log(n), zolang je de n niet te groot neemt.

[jhnbk]

Euhm, het gaat dus eigenlijk over het aantal stappen nodig? (Of zie ik dat weeral fout)

[Vladimir Lenin]

Nou je kan dat ook berekenen, dat is dan de exacte complexiteit, en niet de bigoh notatie, op die manier weet je exact hoveel stappen je moet zetten.

[Cycloon]

Euhm, het gaat dus eigenlijk over het aantal stappen nodig? (Of zie ik dat weeral fout)

Eigenlijk gaat het meer over hoeveel trager het algoritme gaat bij grotere n.

Ik vermoed dat je selection sort wel kent, voor elk element die je bijbrengt zal het algoritme kwadratisch vertragen

\({\cal O}(n^2)\)

. Anderzijds heb je bv radixsort waarbij het groter worden van het elementen het sorteren evenredig doet vertragen met het aantal elementen

\({\cal O}(n)\)

Stel dat je bij selection sort 10 keer meer elementen hebt dan gaat het algoritme 100 keer trager gaan (dit kan je perfect testen), bij radix sort zal het slechts 10 keer trager worden. Je kan nooit zeggen hoe lang een algoritme nodig heeft om tot een resultaat te komen, je kan enkel gaan vergelijken door bv het effect van meer elementen te gaan vergelijken.

[PeterPan]

Efficiënter dan dit kan hij volgens mij niet:

Zeker wel:

Code: Selecteer alles

static int ma,mb,mc,ma1,mb1; // {{ma mb}{mb mc}} representeert de matrix, ma1 en mb1 zijn temp variabelen

void MatrixPower( int n )

{

if (n>1)

{

MatrixPower(n>>1);

// M = M * M

ma1 = ma;

mb1 = mb;

ma = ma*ma + mb*mb;

mb *= ma1+mc;

mc = ma - mb;

}

if (n&1)

{

// M = M * {{1 1}{1 0}}

ma1 = ma;

mc = mb;

ma += mb;

mb = ma1;

}

}

int Fib( int n )

{

ma = mc = 1;

mb = 0;

MatrixPower(n-1);

return ma;

}

Deze is zeker sneller dan die integer [wortel]5 methode van jou.

Euhm, het gaat dus eigenlijk over het aantal stappen nodig? (Of zie ik dat weeral fout)

Was mij uitleg niet duidelijk?

[jhnbk]

Was mij uitleg niet duidelijk?

Jawel hoor. Nu ik alles nog eens terug bekijk is het mij duidelijk geworden.

[Rogier]

Deze is zeker sneller dan die integer [wortel]5 methode van jou.

Kijkend naar de code zou ik dat ook verwachten, maar toch is dat niet het geval (althans als ik hem time met een paar miljoen iteraties in visual studio 2005, release mode, alle optimalisaties aan).

Ik had na bovenstaande verbetering zelfs een nog iets snellere gepost (check daar hoe weinig er eigenlijk nodig is voor die twee matrixvermenigvuldigingen). Die was (wederom tegen mijn verwachting in) bijna even snel als mijn [wortel]5.

Ik heb ook nog een niet-recursieve variant van die matrix methode gedaan en die was wel nagenoeg even snel: (soms iets sneller, soms iets langzamer, maar dat scheelde slechts procentjes)

Code: Selecteer alles

unsigned int Fib( unsigned int n )

{

n--;

unsigned int a=1, b=0, c=1, t;

unsigned int p=1;

while (p<=n) p+=p;

do

{

p >>= 1;

// M = M * M

t = b*b;

b *= a+c;

a = a*a + t;

c = c*c + t;

if (n&p)

{

// M = M * {{1 1}{1 0}}

c = b;

b = a;

a += c;

}

}

while (p>1);

return a;

}