Costo algoritmo di attraversamento particolare

[L\'Esecutore]

Un algoritmo di attraversamento in qualunque ordine di un albero quaternario definito come segue, come lo calcolo?

typedef struct qtnode {
    int cx;
    int cy;
    int tag;
    struct qtnode *nord;
    struct qtnode *sud;
    struct qtnode *ovest;
    struct qtnode *est;
}qtnode;

typedef struct qtnode* tree;

Mi serve calcolare sia costo nel caso migliore che in caso peggiore

[_Claudio]

Originariamente inviato da L\'Esecutore

Un algoritmo di attraversamento in qualunque ordine di un albero quaternario definito come segue, come lo calcolo?

typedef struct qtnode {
    int cx;
    int cy;
    int tag;
    struct qtnode *nord;
    struct qtnode *sud;
    struct qtnode *ovest;
    struct qtnode *est;
}qtnode;

typedef struct qtnode* tree;

Mi serve calcolare sia costo nel caso migliore che in caso peggiore

Se i miei datati ricordi di calcolo della complessità non mi ingannano viene che nel caso peggiore (ogni nodo ha 4 figli tranne le foglie) supponendo di visitare in preordine su n livelli... O(4^n).

I casi medio e migliore dipendono da quanti figli ha in media ogni nodo e quanto l'abero è sparso...

[L\'Esecutore]

E se si tratta di fare una ricerca? l'albero è ordinato su due chiavi

[_Claudio]

Originariamente inviato da L\'Esecutore

E se si tratta di fare una ricerca? l'albero è ordinato su due chiavi

Allora dipende da come è strutturato e da dove è ciò che cerchi, ma se prima di trovare ciò che ti serve devi visitare tutto l'albero allora O(4^l), anche se non avrebbe senso perchè di solito si usano B-tree e derivati.

[wingman87]

Quando poi scrivi la complessità ricordati di specificare che in O(4^n) n è il numero di livelli. Perché nel corso di algoritmi che ho seguito abbiamo sempre specificato le complessità in base al numero di elementi, quindi anche in questo caso la complessità sarebbe stata O(n)

[_Claudio]

Vero... la complessità come l'ho scritta io è in funzione del numero di livelli, l'ho calcolata così perchè poi viene facile anche calcolare la serie geometrica accollata che è funzione del numero di livelli... (ovviamente la serie converge e nel calcolo della complessità peggiore "vince" il 4^l)

[L\'Esecutore]

Ho capito, però mi sorge un dubbio riguardo a "Allora dipende da come è strutturato e da dove è ciò che cerchi, ma se prima di trovare ciò che ti serve devi visitare tutto l'albero allora O(4^l), anche se non avrebbe senso perchè di solito si usano B-tree e derivati."
Probabilmente non mi sono spiegato, ma questo è un derivato da un bst. Si comporta esattamente come un albero di ricerca binario, ha 4 figli perché le chiavi di ordinamento sono 2.

[_Claudio]

Allora sarà O(logn) dove n è il numero di nodi e il log è in base 4... i b-tree esistono proprio perchè l'accesso avviene con complessità log...

[L\'Esecutore]

Vediamo se ho capito giusto:
Una ricerca mi costa O(log4 di n) con n numero di elementi, ma in caso migliore, peggiore o medio?
e un attraversamento completo x una stampa x esempio, O(4^n). Giusto?

[_Claudio]

Originariamente inviato da L\'Esecutore

Vediamo se ho capito giusto:
Una ricerca mi costa O(log4 di n) con n numero di elementi, ma in caso migliore, peggiore o medio?
e un attraversamento completo x una stampa x esempio, O(4^n). Giusto?

Dunque come ordine di complessità l'attraversamento completo costa asintoticamente O(4^l) dove l è il numero di livelli, mentre non asintoticamente bisogna aggiungere un fattore che è una serie geometrica se non vado errato.

La ricerca costa log base 4 di n dove n è il numero di elementi in ogni caso perchè il caso migliore, peggiore o medio dipende dal numero di elementi che hai nell'albero. Puoi fare distinzione tra caso migliore, peggiore o medio se non consideri il numero di elementi ma il numero di livelli che descrivono quanto l'albero è più o meno sparso.