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;
}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?)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).
De complexiteit zegt iets over hoe goed een programma is voor grote waarden.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.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?)
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.
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.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?)
Eigenlijk gaat het meer over hoeveel trager het algoritme gaat bij grotere n.Euhm, het gaat dus eigenlijk over het aantal stappen nodig? (Of zie ik dat weeral fout)
Zeker wel:Efficiënter dan dit kan hij volgens mij niet:
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;
}Was mij uitleg niet duidelijk?Euhm, het gaat dus eigenlijk over het aantal stappen nodig? (Of zie ik dat weeral fout)
Jawel hoor. Nu ik alles nog eens terug bekijk is het mij duidelijk geworden.Was mij uitleg niet duidelijk?
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).Deze is zeker sneller dan die integer [wortel]5 methode van jou.
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;
}