|
|
|
|
Strumenti |
30-10-2017, 18:19 | #1 |
Senior Member
Iscritto dal: Apr 2001
Città: Milano
Messaggi: 3594
|
[C++] costo algoritmico
ciao,
non è per un compito in classe ma una verifica per un mio programma; sto decidendo se adottare questa soluzione in luogo di una ricorsiva ma volevo capirne il costo algoritmico. Non so però se ho messo i costi in modo corretto, n sta per quante volte viene eseguita la riga di codice, 1 per una sola volta. Mi chiedo se alla fine il costo è n^2 Codice:
1: Struct *Nodo = PrimoNodoAlbero(); n: while(Nodo) { n: if(Nodo) { n: p = Nodo->Parent; n: s = Nodo->Testo; n: while(p) n: { n: s+= p->Testo; n: p = p->Parent; } } n: stampa(s); n: Nodo = Nodo->ProssimoNodo(); n: s=""; } |
30-10-2017, 18:31 | #2 |
Senior Member
Iscritto dal: Apr 2001
Città: Milano
Messaggi: 3594
|
ricordavo una cosa del genere ma necessitavo di una conferma, grazie. Mi chiedo però, come mai se invece di innestare 2 while creo due funzioni distinte i tempi migliorano. Ho provato con 1 milione di nodi per vedere delle differenze: 17 minuti quella ricorsiva contro 30 minuti di quella simile all'esempio che ho postato. Potrebbero essere furbate del compilatore oppure, che richiamando una funzione da un'altra ed usando pesantemente lo stack ne benifeciano i tempi di esecuzione?
E' meglio se scrivo il codice per la seconda versione così si capisce di più Codice:
AggiungiSlash(string S1, string S2) { if(UltimoCarattere(S1) != '\\') retStr = S1 + '\\' + S2; else retStr = S1 + S2; return retStr; } /* ----------------------------------------------------------------------- */ OttieniNodo(struct Nodo) { if(Nodo) { struct *p = Nodo->Parent; retStr = Nodo->Testo; while(p) { retStr = AggiungiSlash(p->Text, retStr); p = p->Parent; } } return retStr; } /* ----------------------------------------------------------------------- */ main() { struct Nodo = PrimoNodoAlbero(); // from the first node to last while(Nodo) { stampa(OttieniNodo(Nodo)); Nodo = Nodo->ProssimoNodo(); } } Ultima modifica di misterx : 30-10-2017 alle 18:48. |
31-10-2017, 05:45 | #3 | |
Senior Member
Iscritto dal: Apr 2001
Città: Milano
Messaggi: 3594
|
Quote:
|
|
Strumenti | |
|
|
Tutti gli orari sono GMT +1. Ora sono le: 13:59.