U istom kodu je običan primer koji radi, ali veoma sporo, i jednostavna optimizacija koja se pokazala kao vrlo uspešna za dati problem: samo se pamte vrednosti F(i) u nizu, i ukoliko su već izračunate, ne računaju se ponovo. Zbog osobina izabranog algoritma, broj poziva F(i) je eksponencijalan (čini mi se 3^n), ali na ovaj način se smanjuje na polinomijalan broj.
Program je sledeći (zagrade.c):
#include <stdio.h>
#ifdef BRZO
#define vrati(x) { niz[n]=x; return x; }
#else
#define vrati(x) return x
#endif
typedef long long BROJ;
BROJ *niz;
BROJ F(int n) {
BROJ br,i;
#ifdef BRZO
if (niz[n]) return (niz[n]);
#endif
if ((n==0) || (n==1)) vrati(1);
br=F(n-1);
for (i=1;i<n;i++)
br+= ((F(i-1))*F(n-i));
vrati(br);
}
int main(void) {
int i;
scanf("%d",&i);
#ifdef BRZO
niz=(BROJ *)calloc(i+1,sizeof(BROJ));
#endif
printf("%d: %lld\n",i,F(i));
return 0;
}
Varijanta Zagrade.c je
#define BRZO
#include "zagrade.c"
Razlika u brzini se jasno vidi:
ponedeljak u 16:27 : danilo@avet : ~/rad/razvoj > time echo 20 | ./zagrade
20: 6564120420
real 2m2.100s
user 2m2.080s
sys 0m0.010s
ponedeljak u 16:29 : danilo@avet : ~/rad/razvoj > time echo 20 | ./Zagrade
20: 6564120420
real 0m0.024s
user 0m0.000s
sys 0m0.010s
ponedeljak u 16:29 : danilo@avet : ~/rad/razvoj >
E, problem je što broj mogućnosti prevazilazi opseg int64-a već na 36, a ,,brzi'' program kvadratno usporava, i tada i dalje ima neprimetno vreme izvršavanja. Nadam se da se slažete da je O(n^2) prilično dobar rezultat za ovakav program (nisam dokazao, ali rast utrošenog CPU vremena mi ukazuje na to, a ne rešavaju mi se rekurentne jednačine :).
I primetite da ovaj program vraća pogrešnu vrednost za nula zagrada, ali to se lako proveri posebno (vraća 1, umesto 0). Razlog za to provalite sami :)
Nadam se da će neko uraditi bolje! (npr. bez upotrebe O(n) memorije, a ista složenost; ili manja složenost).
Toliko
PS. Nadam se da je program ispravan :)