PDA

Visualizza la versione completa : [C] Alg. Horner - compl. tempo e spazio


Metallica
19-02-2004, 10:17
Qual'Ŕ la complessitÓ di tempo e spazio in questo programmino?


#include <stdio.h>
#include <malloc.h>

/* PROTOTIPO DELLA FUNZIONE */
void horner(float *coeff, int n, float c, float *ris);

/* PROGRAMMA CHIAMANTE */
main(){

/* DICHIARAZIONE VARIABILI */
int i, n;
float *coeff, r, c;

/* LETTURA DEL GRADO DEL POLINOMIO */
printf("Inserire il grado del polinomio: ");
scanf("%d", &n);

/* ALLOCAZIONE DINAMICA DELLA MEMORIA */
if(!(coeff = (float *)malloc(n*sizeof(float))))
abort();

/* LETTURA DEI COEFFICIENTI DI A */
printf("\nInserire uno ad uno i valori dei coefficienti: \n");
for(i = 0; i <= n; i++)
{
printf("Inserire il valore del coeff %d: ", i);
scanf("%f", &coeff[i]);
}

/* LETTURA DELLA VARIABILE c */
printf("\nInserisci il valore del punto c: ");
scanf("%f",&c);

/* RICHIAMO DELLA FUNZIONE */
horner(coeff, n, c, &r);

/* STAMPA DEL RISULTATO */
printf("\nIl polinomio vale: %f \n", r);

/* RILASCIO DELLA MEMORIA OCCUPATA DALL'ARRAY */
free(coeff);
}

/****************** SPECIFICHE FUNZIONE *************************/
void horner(float *coeff, int n, float c, float *ris)
{
int i, p;
p = coeff[n];
for(i = n-1; i >= 0; i--)
{
p = p * c + coeff[i];
}
*ris = p;
}

Io per il tempo mi trovo T(n)=O(n) ma per lo spazio non lo s˛...

ellecubo
19-02-2004, 11:11
mmh.....
T(n)=O(n)=n
S(n)=n+4=O(n)

Loading