PDA

Visualizza la versione completa : [ALGORITMI] Come dimostrare complessitÓ del problema Torri di Hanoi


gabama
07-07-2009, 11:08
Vorrei porre alcune domande teoriche su liste in c:
1)sono riuscito a dimostrare le complessitÓ in tempo per gli ordinamenti ,mergesort,quicksort, e per le torri di hanoi.Non riesco per˛ fare altrettanto per quanto riguarda lo spazio

il primo ha complessitÓ log n,come il quicksort

le torri hanoi hanno complessitÓ O(n)

come posso dimostrare questa cose ?

Come ultima domanda perchŔ una ricorsione non di coda Ŕ meglio in certe situazioni rispetto alla ricorsione di coda?

LeleFT
07-07-2009, 13:42
Queste non sono domande di programmazione, sono domande che riguardano la teoria degli algoritmi. Il fatto che tu le abbia sviluppate in C non c'entra con il linguaggio in se, visto che la teoria degli algoritmi prescinde dal linguaggio di implementazione.

E' pur vero che molte volte si sono trattati anche argomenti puramente teorici sugli algoritmi, ma Ŕ necessario scindere ciascuna domanda in una discussione a parte.

Modifico il titolo per questa discussione (togliendo il riferimento al linguaggio, non essendo necessario in questo contesto), ma limito tale discussione alla prima domanda: come dimostrare che il problema delle torri di Hanoi ha complessitÓ O(n).


Per le altre questioni, apri una discussione a parte.

PS: tieni presente che generalmente non si producono soluzioni intere... quindi, fai dei tentativi e postali, chiedendo lumi su di essi.


Ciao. :ciauz:

Loading