Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. 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