Domande Ricorsioni liste in C

[gabama]

Ragazzi,spero che qualcuno mi possa dare consigli perchè è molto importante
TORRI HANOI

Void nuove(int n,int start,int and,int trip){
	If(n>0){
		Nuove(n-1,start,tmp,and);
	  Alfa   Printf(“%d”->”%d”\n,start,and);
		Nuove(n-1,tmp,and,start)}   beta

Secondo me non è ricorsiva lineare ed è di coda
E’ corretto?
Sono giuste le complessità?

Complessità in spazio O(n) ,perché è proporzionale agli elementi n
Complessità in tempo è data dall’ altezza dell’ albero e 2^n-1.Quindi è dato dal numero di chiamate ricorsive
---------------------
MERGESORT

Typedef struct listnode
{ListEntry entry;
struct listnode * next;
}ListNode;

Typedef struct ListNode
{ListEntry entry;
struct listnode * head;
int count;
}List;

Typedef struct ListEntry
{??,Key;
}ListEntry;

Void mergesort(List *list){
List * secondhalf;   puntatore testa
If ListSize(list)>1
{Divide(list,&secondhalf);
Mergesort(list);
Mergesort(&secondhald);
Mergesort(list,&secondhalf,list);}}

Void divide(List *list,List *secondhalf){
ListNode *current;* midpoint;
If((midpoint=list->head)==head)
Secondhalf->head=NULL;
Else{for(current=midpoint->next;current)
{current=current->next;
If(current){
Midpoint=midpoint->next;
Current=current->next;}}
Secondhalf->head=midpoint->next;
Midpoint->next=null;}}

Complessità in spazio O(log 2 n) ,sostanziale rispetto ai O(n^2)
Complessità in tempo è data dall’ altezza dell’ albero per n.Quindi è O(n*log 2n)

E’ ricorsiva lineare ?e’ di coda?
--------------------------
QUICKSORT

Void Quicksort(List * list){
Rec Quicksort(list,0,list-count-1);}

Void Rec Quicksort (List * list,int low,int high)
{int pivotpos;
If(low<high)
{pivotpos=partition(list,low,high);
Rec Quicksort(list,low,pivotpos-1);
Rec Quicksort(list,pivotpos+1,high);}}

Complessità in spazio O(n) ,ma perché?
Complessità in tempo O(n^2),ma perché?
E’ ricorsiva lineare ?e’ di coda?

[YuYevon]

Allora innanzitutto per quanto riguarda la linearità delle ricorsioni, direi che nessuno di questi algoritmi è ricorsivo lineare visto che tutti hanno più di una chiamata ricorsiva a sé stessi.

Per quanto ne so, non si può parlare in nessun caso (di quelli proposti) nemmeno di "ricorsione di coda" perché questa si ha quando la chiamata ricorsiva è l'ultima istruzione dell'algoritmo.

Per quanto riguarda le complessità di tempo:

TORRI HANOI
...
Complessità in tempo è data dall’ altezza dell’ albero e 2^n-1.

non ho mai lavorato sull'algoritmo delle torri di Hanoi, ma lo conosco teoricamente. In pratica per trovare quella complessità (asinototica) di tempo dovresti risolvere un'equazione di ricorrenza che è la sequente:

T(n) = 0 se n = 0;
T(n) = 2T(n-1) + c se n > 0

dove c è una costante. Comunque dovrebbe essere effettivamente esponenziale, tra l'altro l'algoritmo delle torri di Hanoi se non mi sbaglio va risolto con una tecnica di backtracking che porta sempre a complessità esponenziali. In ogni caso, bisogna risolvere quella ricorrenza e non si può dire così, a impressione.

MERGESORT
...
Complessità in spazio O(log 2 n) ,sostanziale rispetto ai O(n^2)
Complessità in tempo è data dall’ altezza dell’ albero per n.Quindi è O(n*log 2n)

la prima affermazione non l'ho capita proprio...

la seconda è corretta, il Merge Sort ha una complessità di tempo che non degrada mai a quella quadratica.

QUICKSORT
...
Complessità in spazio O(n) ,ma perché?

scusa, in genere come fai a determinare la complessità di spazio? Non vedi forse la dimensione delle strutture dati? Nel caso del Quick Sort non hai semplicemente una lista con n nodi? Quindi perché ti stupisce che sia O(n) ?

Complessità in tempo O(n^2),ma perché?

Il Quick Sort, essenzialmente, è un algoritmo a complessità lin-log ( cioè O(nlogn) ) perché è basato sulla tecnica del divide et impera (come il merge sort). Se fosse a complessità quadratica sarebbe uno dei "peggiori" (alla pari di Insertion Sort, bubble sort e altri), mentre invece al contrario è uno dei migliori (tant'è che in alcuni linguaggi di programmazione esistono delle funzioni di ordinamento che implementano proprio il Quick Sort).

Il fatto che sia O(n^2) dipende da una questione MOLTO sottile, che non è assolutamente trattabile in un topic su un forum... ci sono scienziati che ci hanno scritto interi capitoli sulla complessità del Quick Sort.

Se vuoi qualche idea, ti posso suggerire queste slide:

http://cvprlab.uniparthenope.it/staf...2009/ASD-6.pdf
http://cvprlab.uniparthenope.it/staf...2009/ASD-7.pdf

[gabama]

YuYevon,scusa se ti rispondo solo adesso,avevo già visto il messaggio prima ,ma non ho fatto in tempo.
Dirti grazie e che sei stato gentilissimo mi sembra poco per tutto quello che mi hai "dettagliato",ti ringrazio molto
grazie ancora
ciao