C - invariante e complessità

[gabama]

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

[YuYevon]

Ciao,

guarda se non posti bene il codice (cioè almeno riportandolo tra i tag "code") dubito che in molti avranno voglia di leggerselo, tra l'altro è anche scritto nel regolamento che sarebbe carino rispettare... comunque per adesso stavo dando un'occhiata al primo algoritmo, che riscritto in maniera più guardabile è

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;
}

e direi che, come dicevi, sia complessità di spazio che di tempo sono O(n), e più precisamente:

la complessità di tempo è O(n) dove n è la lunghezza della lista più lunga (o delle due liste se hanno uguale lungezza). Analiticamente sarebbe T(m, n) = m + n, dove appunto m è la lunghezza della prima lista e n quella della seconda (con eventualmente m = n), ma a livello asintotico questo conta poco e diciamo semplicemente che la complessità di tempo è lineare, ossia O(n);

la complessità di spazio è O(n), dove n è sempre la lunghezza della lista più lunga. Valgono considerazioni molto simili a quelle fatte per la complessità di tempo: dette m e n le lunghezze delle due liste, analiticamente avremmo una complessità di spazio S(m, n) = m + n, ma ancora una volta a livello asintotico ci basta dire che è O(n).

Per quanto riguarda l'invariante di ciclo, anche hai azzeccato... potremmo dire più precisamente che l'invariante sia questa:

"all'i-esima iterazione, la variabile "somma" contiene la somma dei prodotti dei primi i elementi delle due liste".

Per il secondo algoritmo... il consiglio è non solo di postarlo meglio ma anche di specificare cosa fa e cosa sono le variabili pos, x, y e z perché è un po' difficile andare a intuito.

[gabama]

YuYevon ti ringrazio infinitamente,sei troppo gentile,e mi scuso se non ho usato i tag.Il secondo è così,duplica i nodi compresi tra x e y e multipli di z

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); 
}

[YuYevon]

A parte che c'è qualcosa che ancora non mi convince su quest'algoritmo (tanto per dirne una, quella variabile "int s" che non viene mai usata), direi che per quanto riguarda complessità di tempo e spazio siamo sempre lì.

La ricorsione procede per tutta la lunghezza della lista, quindi se questa è n ancora una volta avremo una complessità di tempo asintotica pari a O(n).

Per la complessità di spazio, abbiamo una lista di input di lunghezza n e una di output la cui lunghezza è variabile perché, se ho capito bene, avrà gli stessi nodi di quella di input che sono compresi tra x e y e che sono multipli di z. Quindi diciamo che nel caso migliore non ci sarà nulla da duplicare (perché ad esempio nessuno è multiplo di z o nessuno è compreso tra x e y) e allora la lunghezza della lista di output sarà pari a 0, quindi avremo 0 + n = n che asintoticamente è ovviamente O(n). Nel caso peggiore, invece, avremo duplicato tutti i nodi della lista, e allora ci ritroveremo con una lista di lunghezza pari esattamente a quella della lista di input, quindi n, e in totale n + n = 2n che asintoticamente è sempre lineare O(n), quindi in tutti i casi anche la complessità asintotica di spazio è O(n).

Ovviamente, quando una complessità asintotica è uguale sia nel caso migliore che nel caso peggiore, cioè quando è (ad esempio) sia Ω(n) che O(n), allora diciamo che è complessivamente Θ(n)... ma vabbè o-o"

[gabama]

YuYevon ti ringrazio molto,se dovessi ancora avere dei dubbi spero avrai ancora voglia di rispondermi,
grazie davvero