C - Liste e complessità

[gabama]

So che questa domanda non è direttamente legata alla programmazione,però spero qualcuno mi dia solo questo paio di conferme che ho bisogno,poi il messaggio può tranquillamente essere cancellato se non rientra nelle regole del Forum.Vi ringrazio in anticipo e mi scuso per l' "intrusione"
---ITERAZIONE---

int massimo(node *l1,node *l2)
{int max;
if((l1==NULL) && (l2==NULL)) return 0;
while((l1!=NULL) && (l2!=NULL)){
    if((l1->data+l2->data)>max) max=l1->data+l2->data;
    l1=l1->next;
    l2=l2->next;
  }

while((l1!=NULL) && (l2==NULL)){
    if(l1->data>max) max=l1->data;
    l1=l1->next;

  }

while((l1==NULL) && (l2!=NULL)){
    if(l2->data>max) max=l2->data;
    l2=l2->next;

  }



return max;

}

con questa lista voglio ritornare il valore max,il codice funziona,ma vorrei sapere se l 'invariante è " al generico passo il max è la max somma trovata fino a quel punto"
La complessità in tempo è O(n+m) o semplicemente n dove n è il massimo sumero di nodi tra l1 o l2?
Anche in spazio è così,ma perchè?

---RICORSIONE---

node *alternata(node *l1,node *l2,int pos){
node *p;
if((l1==NULL) && (l2==NULL))  return NULL;
else if((l1!=NULL) && (l2==NULL)){

   p=newnode();
   p->data=l1->data;
   p->next=somma(l1->next,l2,pos+1);
   return p;}



else if((l1==NULL) && (l2!=NULL)){

   p=newnode();
   p->data=l2->data;
   p->next=somma(l1,l2->next,pos+1);
   return p;}




else if((l1!=NULL) && (l2!=NULL)){
   if(pos%2!=0){
   p=newnode();
   p->data=l1->data;
   p->next=somma(l1->next,l2,pos+1);
   return p;}
   else{
   p=newnode();
   p->data=l2->data;
   p->next=somma(l1,l2->next,pos+1);
   return p;}

   }}

Qui duplica i valori presi alternativamente dalle 2 liste
Stessa cosa per il tempo,e in spazio anche O (n) dove n è il massimo numero di record di attivazione contemporaneamente aperti ?

Vi prego ragazzi,è molto importante!

[YuYevon]

Originariamente inviato da gabama
con questa lista voglio ritornare il valore max,il codice funziona,ma vorrei sapere se l 'invariante è " al generico passo il max è la max somma trovata fino a quel punto"

Va bene, anche se tu vuoi determinare la massima somma tra elementi corrispondenti, e non il "valore max", come hai detto.

Originariamente inviato da gabama
La complessità in tempo è O(n+m) o semplicemente n dove n è il massimo sumero di nodi tra l1 o l2?
Anche in spazio è così,ma perchè?

La complessità di tempo, analiticamente, è n + m, dove n e m solo le lunghezze delle due liste. Da un punto di vista asintotico, però, quando hai una somma di termini si considera quello di grado massimo. Ora se m e n sono dello stesso ordine, ha senso dire T(n) = O(n), e mi sembra che sia proprio questo il caso. Se invece m risultasse di tutt'altro ordine rispetto a n, tipo m = n^2, allora dovresti necessariamente dire T(n) = O(n^2), questo perché di fatto n + m risulterebbe essere n + n^2, e il termine di grado massimo tra questi due è n^2, naturalmente.

Per la complessità di spazio valgono esattamente le stesse considerazioni, visto che anche questa dipende dalla lunghezza delle liste.

Originariamente inviato da gabama
Qui duplica i valori presi alternativamente dalle 2 liste
Stessa cosa per il tempo,e in spazio anche O (n) dove n è il massimo numero di record di attivazione contemporaneamente aperti ?

Hai parlato di ricorsione, ma mi sa che hai sbagliato a scrivere il nome della funzione: l'hai chiamata "alternata", ma poi nel suo codice non c'è alcuna attivazione della stessa funzione. Forse la volevi chiamare "somma"?

In ogni caso per determinare la complessità asintotica di un algoritmo ricorsivo va impostata un'equazione di ricorrenza, in generale. Facendo una stima approssimativa, comunque, la complessità di tempo risulta appunto n + m perché di fatto si scorrono ancora una volta entrambe le liste, poi vabbè sulla complessità asintotica valgono le stesse considerazioni di sopra. La complessità di spazio sarebbe m + n + (m+n), cioè m per la prima lista, n per la seconda e m+n per quella creata. Ancora una volta, se m e n hanno lo stesso ordine, risulta in definitiva S(n) = O(n).

Originariamente inviato da gabama
Vi prego ragazzi,è molto importante!

In generale sul forum non si apprezza molto sentire parole come "importante" o "urgente", perché tutti sarebbero liberi di dirlo per dare priorità ai loro problemi :-)
Piuttosto ti consiglio di mantenere la calma, e soprattutto la prossima volta posta il codice indentato un po' meglio perché così è difficile da leggere.

Comunque, queste domande e questi algoritmi non mi sembrano affatto nuovi... non avevi già aperto una discussione identica un bel po' di tempo fa?

[gabama]

grazie!
quindi riassumendo,
l' invariante al generico passo è la max somma tra elementi corrispondenti
in iterazione posso dire che la complessità in tempo è O(n) dove n è il valore maggiore tra n e m,no?
Però per lo spazio è uguale,ok,ma come devo dire?In ricorsione ci sono al massimo m o n record di attivazione contemporaneamente aperti,ma in iterazione?

Per ricorsione ok

Grazie e spero ancora in una vostra gentilezza

[bitman]

forse ho capito male ma..
nel primo codice (iterativo) la complessità non è O( n + m + min(n,m) ) ?
oppure in altra forma: O( 2n + m ) dove n è il più piccolo dei due?

[gabama]

perchè?

[YuYevon]

Originariamente inviato da bitman
forse ho capito male ma..
nel primo codice (iterativo) la complessità non è O( n + m + min(n,m) ) ?
oppure in altra forma: O( 2n + m ) dove n è il più piccolo dei due?

Non c'è bisogno di ragionarci troppo, vengono scorse tutte e due le liste (con opportuni controlli, ma non conta) quindi la complessità risulta n + m. E come dicevo, se n e m sono dello stesso ordine, in definitiva abbiamo T(n) = O(n).

Originariamente inviato da gabama
Però per lo spazio è uguale,ok,ma come devo dire?In ricorsione ci sono al massimo m o n record di attivazione contemporaneamente aperti,ma in iterazione?

Intendi nel primo algoritmo? Lì hai due liste con n e m record, qual è il problema?

[gabama]

intendevo anche in iterazione ho m + n record di attivazione contemporaneamente aperti?

[bitman]

niente ho letto male :P
avevo capito che i secondi due cicli ricontrollavano entrambi gli array da capo, invece controllano solo gli elementi rimasti