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

Тема в разделе "Общие вопросы по С и С++", создана пользователем Guest_, 15 янв 2006.

Статус темы:
Закрыта.
  1. Guest_

    Guest_ Гость

    Народ, может кто знает, как определить априорную и апостериорную временную и ёмкостную сложность программы? и как это реализовать в с++?
    код программы следующий:
    Код (Text):
    #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;
    }
     
  2. Guest_

    Guest_ Гость

    Код (Text):
     
    #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;
    }
     
Загрузка...
Похожие Темы - Оценка временной сложности
  1. anna
    Ответов:
    4
    Просмотров:
    259
  2. Supermaximus
    Ответов:
    3
    Просмотров:
    1.902
  3. EmptyR
    Ответов:
    14
    Просмотров:
    4.402
  4. Cleric-Lviv
    Ответов:
    12
    Просмотров:
    4.275
  5. slavon-x86
    Ответов:
    8
    Просмотров:
    4.493
Статус темы:
Закрыта.

Поделиться этой страницей