всем приветы! кто-нибудь может пдсказать априорнуюи апостериорную временные и ёмкостные сложности следующей программы:

Код

#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; }

ЭЭэх... Кто бы мне ещё сказал что это такое...

Гость_Женя
Что за первые две фишки не слышал, а вот последнии считаются так. Емкостная сложность оценивается подсчетом, сколько было выделенно и использованно памяти для программы(в том числе heap-memory and stack-memory)-подсчитывается просто - перегружаются new and delete для heap, результаты обработки суммируются с константными размерами stack-переменных.
Временная сложность определяется с помощью установки таймера.

Цитата

Емкостная сложность оценивается подсчетом, сколько было выделенно и использованно памяти для программы(в том числе heap-memory and stack-memory)-подсчитывается просто - перегружаются new and delete для heap, результаты обработки суммируются с константными размерами stack-переменных. Временная сложность определяется с помощью установки таймера.

Это точно пройдёт, если программу предполагается компилировать, используя только один конкретный компилятор, и выполнять, используя одну конкретную машину.

Возможно, придётся все считать вручную.

Это сообщение отредактировал(а) nworm - 15.1.2006, 20:12

думаю ,что под априорной оценкой временой сложности выполнения программы подразумевается оценка этого времени ещё до запуска самой программы... то бишь как-то подсчитать время, которое уйдет на выполнение программы ещё до того, как она будет выполнена...

под апостериорной соответственно после её выполнения...

Цитата

думаю ,что под априорной оценкой временой сложности выполнения программы подразумевается оценка этого времени ещё до запуска самой программы... то бишь как-то подсчитать время, которое уйдет на выполнение программы ещё до того, как она будет выполнена... под апостериорной соответственно после её выполнения...

Да, похоже. Поисковик даёт примерно такое толкование

1. априорная временная сложность = асимптотическая оценка временной сложности
2. апосториорная = оценка сложности алгоритма с точностью до мультипликативных констант, сделанных для конкретной машины.

Аналогично, ёмкостная сложность.

свременной оценкой сложности я разобрался...вы правы... апостериорная- это надо просто таймерм засекать в начале и конце выполнения алгоритма...априорная, мне показали, там сложные какие товычисления...метод гаусса какой то для первых производных...сам не знаю, откудаони берутся..
а вот какая ёмкостная сложность? допустим априорную я найду..как я понял, надо просто посчитать кол-во памяти, выделяемое под все используемые главные переменные..а вот апостериорную как? ujdjhzn? надо ещё учитывать динамическое выделение, и ещё много всего..так и не понял..никто не знает?

Откуда метод Гаусса? Программа как-то с ним связана?
Там, по-моему, надо просто операции считать (сложения, вычитания и т.п.) причём некоторыми операциями принебрегают. Для многих алгоритмов оценки известны (там ещё символы O-большое применяются).

2 nworm: ну например если сложность линейная, то сложность соответственно: С1*N+C2. вот эти с1 и с2 высчитываются методом гаусса..не спрашивай меня как, не знаю...если интересно, есть вариант другой проги с посчитанной этой фигнёй..
но мне это обещали сделать...а вот с ёмкостной сложностью...особенно с апостериорной...никто не знает...