si consideri la seguente procedura iterativa.
#include<iostream.h> int main() { int n; cout << "Dammi n: "; cin >> n; cout << endl; long long int T[n +1]; T[0] = 1; cout << "T[0] = " << T[0] << endl; for(int k=1; k<=n; k++) { T[k] = T[k-1]+T[k-1]; cout << "T[" << n << "] = " << T[n] << endl; } }
Si stabilisca l'ordine di crescita del tempo di calcolo della procedura proposta. Si stabilisca l'ordine di crescita della memoria impiegata dalla procedura proposta.
#include<iostream.h> long long int T(int n) { if(n==0) return 1; return T(n-1) + T(n-1); } int main() { int n; cout << "Dammi n: "; cin >> n; cout << endl; cout << "T[" << n << "] = " << T(n) << endl; }
Si stabilisca l'ordine asintotico di crescita per il tempo di calcolo della procedura proposta dal professor Tortoise. Si stabilisca l'ordine di crescita della memoria impiegata dalla procedura di Tortoise.
Complemento 6+ Per questa particolare ricorrenza ( ), è possibile pensare ad un accorgimento che consenta di ottenere un buon tempo di calcolo anche per la procedura ricorsiva. Sapresti indicare quale?