[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]

Originariamente inviato da Antonio23

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]

Originariamente inviato da Antonio23

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)?