Questo sito utilizza cookies, anche di terze parti, per mostrare pubblicitÓ e servizi in linea con il tuo account. Leggi l'informativa sui cookies.
Username: Password: oppure
C/C++ - ComplessitÓ e invariante ciclo liste in C
Forum - C/C++ - ComplessitÓ e invariante ciclo liste in C

Avatar
gabama (Normal User)
Rookie


Messaggi: 26
Iscritto: 12/04/2009

Segnala al moderatore
Postato alle 13:05
Martedý, 16/06/2009
Ho due funzioni che operano su liste in iterazione e ricorsione e vorrei se possibile alcune conferme
ITERAZIONE
  int prodotto (node *l1,node *l2)
{
int somma=0;
if((l1==NULL) && (l2==NULL)) return NULL;
while((l1!=NULL) && (l2!=NULL)){
    somma=somma+l1->data*l2->data;
    l1=l1->next;
    l2=l2->next;
    }

while((l1!=NULL) && (l2==NULL)){
    somma=somma+l1->data;
    l1=l1->next;

    }

while((l1==NULL) && (l2!=NULL)){
    somma=somma+l2->data;
    l2=l2->next;

    }



return somma;}

per l' invariante Ŕ corretto dire che la somma Ŕ compresa tra 0 e la somma fino al valore corrente sommato?
La complessitÓ in tempo e spazio Ŕ O(n) per entrambi,ma perchŔ?PerchŔ al massimo ci sono n elementi?

RICORSIONE
node *somma(node *l1,int pos,int x,int y,int z){
node *p;int s=0;
if (l1==NULL) return NULL;
else if((pos>x) && (pos<y) && (l1->data%z==0)){
    p=newnode();
    p->data=l1->data;
    p->next=somma(l1->next,pos+1,x,y,z);
    return p;}
    return somma(l1->next,pos+1,x,y,z);
}
vorrei se possibile la stessa conferma per le complessitÓ
Ringrazio in anticipo chiunque voglia rispodermi

PM Quote