[C++] costo algoritmico

[misterx]

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

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

[misterx]

doppio loop, costo O(N^2)

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ù :)

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

[misterx]

una cosa e' la complessita' teorica dell'algoritmo, un'altra sono "il numero di cicli" della tua implementazione su una particolare architettura. per dare una risposta completa dovresti osservare l'assembly prodotto dal compilatore, capire quali ottimizzazioni sta facendo, etc.

di sicuro c'è di mezzo qualche ottimizzazione; ma a colpo d'occhio, non ti sembra che anche la seconda versione sia una O(N^2)?