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?