[ALGORITMI] Costo ricerca in un ABR

HoldenCaulfield1987 · 16-06-2011, 10:48

Spero di essere nella sezione più appropriata.

Sto studiando dal punto di vista algoritmico gli alberi binari di ricerca.
So che ad esempio per una ricerca il tempo di esecuzione è O(h), dove h è l'altezza dell'albero.
La cosa che onestamente mi fa impazzire è il COME viene calcolato quel tempo di esecuzione.
M spiego meglio:
quel tempo di esecuzione indica il numero di nodi visitati oppure il numero di chiamate ricorsive effettuate a partire dal figlio (sx o dx che sia) della radice?
A me verrebbe più facile pensare al numero di nodi visitati, però cosi non considero la visita al nodo di partenza, ovvero al nodo radice.
E' anche vero però che asintoticamente dire h (quindi tutti i nodi interni e la foglia) + 1 (la radice) è uguale a dire solo h.

Come forse avrete capito ho un po' di confusione a riguardo.
Mi date una mano?

Grazie

SerMagnus · 16-06-2011, 11:06

il costo della ricerca binaria è log(2) n.

il calcolo viene effettuato tenendo conto delle sole istruzioni dominanti dell'algoritmo

HoldenCaulfield1987 · 16-06-2011, 11:10

Si, ma se il costo di una ricerca/cancellazione/inserimento è O(h), in h è considerata la visita del nodo radice (ma nascosta dalla notazione asintotica), oppure non viene considerata?

SerMagnus · 16-06-2011, 11:37

beh siccome la ricerca binaria dimezza ad ogni passo la dimensione della sequenza da valutare, ti troverai comunque che ad ogni passo valuterà, log(2) n, dove con n è inidicata la grandezza della sequenza corrente, o in altri termini la profondità dell'albero binario a partire dal nodo corrente

HoldenCaulfield1987 · 16-06-2011, 11:49

Quindi se ho capito bene tu calcoli:
un numero c di operazioni di costo costante per la visita del nodo radice + il costo delle visite ricorsive ai figli.

SerMagnus · 16-06-2011, 15:35

ora nn ricordo di preciso, però in realtà durante il cacolo della complessità il numero di chiamate ricorsive non rientra nel cacolo, salvo se questa non fa parte di una delle istruzioni dominanti.

in realtà per la ricerca binaria devi considerare il numero di passi per discendere l'albero, a partire della seguenza in ingresso, ecco come esce fuori il valore di log(2) n

al generico passo k, ti trovi n/2^(k-1)

16-06-2011, 10:48	#1
HoldenCaulfield1987 Member Iscritto dal: May 2010 Messaggi: 157	[ALGORITMI] Costo ricerca in un ABR Spero di essere nella sezione più appropriata. Sto studiando dal punto di vista algoritmico gli alberi binari di ricerca. So che ad esempio per una ricerca il tempo di esecuzione è O(h), dove h è l'altezza dell'albero. La cosa che onestamente mi fa impazzire è il COME viene calcolato quel tempo di esecuzione. M spiego meglio: quel tempo di esecuzione indica il numero di nodi visitati oppure il numero di chiamate ricorsive effettuate a partire dal figlio (sx o dx che sia) della radice? A me verrebbe più facile pensare al numero di nodi visitati, però cosi non considero la visita al nodo di partenza, ovvero al nodo radice. E' anche vero però che asintoticamente dire h (quindi tutti i nodi interni e la foglia) + 1 (la radice) è uguale a dire solo h. Come forse avrete capito ho un po' di confusione a riguardo. Mi date una mano? Grazie

16-06-2011, 11:06	#2
SerMagnus Senior Member Iscritto dal: Sep 2005 Messaggi: 1400	il costo della ricerca binaria è log(2) n. il calcolo viene effettuato tenendo conto delle sole istruzioni dominanti dell'algoritmo

16-06-2011, 11:10	#3
HoldenCaulfield1987 Member Iscritto dal: May 2010 Messaggi: 157	Si, ma se il costo di una ricerca/cancellazione/inserimento è O(h), in h è considerata la visita del nodo radice (ma nascosta dalla notazione asintotica), oppure non viene considerata?

16-06-2011, 11:37	#4
SerMagnus Senior Member Iscritto dal: Sep 2005 Messaggi: 1400	beh siccome la ricerca binaria dimezza ad ogni passo la dimensione della sequenza da valutare, ti troverai comunque che ad ogni passo valuterà, log(2) n, dove con n è inidicata la grandezza della sequenza corrente, o in altri termini la profondità dell'albero binario a partire dal nodo corrente

16-06-2011, 11:49	#5
HoldenCaulfield1987 Member Iscritto dal: May 2010 Messaggi: 157	Quindi se ho capito bene tu calcoli: un numero c di operazioni di costo costante per la visita del nodo radice + il costo delle visite ricorsive ai figli.

16-06-2011, 15:35	#6
SerMagnus Senior Member Iscritto dal: Sep 2005 Messaggi: 1400	ora nn ricordo di preciso, però in realtà durante il cacolo della complessità il numero di chiamate ricorsive non rientra nel cacolo, salvo se questa non fa parte di una delle istruzioni dominanti. in realtà per la ricerca binaria devi considerare il numero di passi per discendere l'albero, a partire della seguenza in ingresso, ecco come esce fuori il valore di log(2) n al generico passo k, ti trovi n/2^(k-1)

Strumenti
Mostra una versione stampabile Invia questa pagina per email