Оценка временной сложности программы

[Guest_]

Народ, может кто знает, как определить априорную и апостериорную временную и ёмкостную сложность программы? и как это реализовать в с++?
код программы следующий:

#include <cstdio>
#include <iostream>
#include <cstring>

using namespace std;

typedef long long ll;

ll f[16];
ll a[16];

int d,n,m;

ll m1[16][16];
ll m2[16][16]; 
ll m3[16][16];

void umnmat(ll m1[16][16],ll m2[16][16]) {
int i,j,k;
ll z;
for (i=0;i<d;++i) {
for (j=0;j<d;++j) {
m3[i][j] = 0;
for (k=0;k<d;++k) {
z = (m1[i][k]*m2[k][j])%m;
m3[i][j] = (m3[i][j]+z)%m;
}
}
}
for (i=0;i<d;++i)
for (j=0;j<d;++j)
m1[i][j] = m3[i][j];
}

int main() {

while (1) {
scanf("%d %d %d",&d,&n,&m);
if (!d && !n && !m)
break;

int i;
int x;
for (i=0;i<d;++i) {
scanf("%d",&x); 
x %= m;
a[d-i-1] = x;
}
for (i=0;i<d;++i) {
scanf("%d",&x);
x %= m;
f[i] = x;
}

if (n<=d) {
printf("%d\n",int(f[n-1]));
continue;
}

n -= d;
memset(m1,0,sizeof(m1));
for (i=0;i<d;++i)
m1[i][i] = 1;

int j;
for (i = 1; i < d; ++i) {
for (j = 0; j < d; ++j) {
m2[j][i-1] = (j==i);
}
}
for (i=0;i<d;++i)
m2[i][d-1] = a[i];

while (n) {
if (n%2) {
umnmat(m1,m2);
}
umnmat(m2,m2);
n /= 2;
}

ll ans = 0;
ll xx;
for (i=0;i<d;++i) {
xx = (f[i]*m1[i][d-1])%m;
ans = (ans+xx)%m;
}

printf("%d\n",int(ans));
}

return 0;
}

 

[Guest_]

#include <cstdio>
#include <iostream>
#include <cstring>

using namespace std;

typedef long long ll;

ll f[16];
ll a[16];

int d,n,m;

ll m1[16][16];
ll m2[16][16]; 
ll m3[16][16];

void umnmat(ll m1[16][16],ll m2[16][16]) {
   int i,j,k;
   ll z;
   for (i=0;i<d;++i) {
       for (j=0;j<d;++j) {
           m3[i][j] = 0;
           for (k=0;k<d;++k) {
               z = (m1[i][k]*m2[k][j])%m;
               m3[i][j] = (m3[i][j]+z)%m;
           }
       }
   }
   for (i=0;i<d;++i)
       for (j=0;j<d;++j)
           m1[i][j] = m3[i][j];
}

int main() {

   while (1) {
       scanf("%d %d %d",&d,&n,&m);
       if (!d && !n && !m)
           break;

       int i;
       int x;
       for (i=0;i<d;++i) {
           scanf("%d",&x); 
           x %= m;
           a[d-i-1] = x;
       }
       for (i=0;i<d;++i) {
           scanf("%d",&x);
           x %= m;
           f[i] = x;
       }

       if (n<=d) {
           printf("%d\n",int(f[n-1]));
           continue;
       }

       n -= d;
       memset(m1,0,sizeof(m1));
       for (i=0;i<d;++i)
           m1[i][i] = 1;

       int j;
       for (i = 1; i < d; ++i) {
           for (j = 0; j < d; ++j) {
               m2[j][i-1] = (j==i);
           }
       }
       for (i=0;i<d;++i)
           m2[i][d-1] = a[i];

       while (n) {
           if (n%2) {
               umnmat(m1,m2);
           }
           umnmat(m2,m2);
           n /= 2;
       }

       ll ans = 0;
       ll xx;
       for (i=0;i<d;++i) {
           xx = (f[i]*m1[i][d-1])%m;
           ans = (ans+xx)%m;
       }

       printf("%d\n",int(ans));
   }

   return 0;
}