Domanda sulla complessità dell'algoritmo Barnes-Hut

0

Un algoritmo comune utilizzato nei calcoli gravitazionali N-corpo con un grande numero di corpi (stelle in una galassia, galassie nell'universo, ecc.) è Barnes-Hut algoritmo, che raccoglie le particelle in un octree per calcoli approssimativi di massa delle forze gravitazionali tra aree distanti. La complessità di questo algoritmo è O (N log N), rispetto a O (N ^ 2) di un calcolo diretto più realistico tra tutte le coppie di punti.

Sto cercando di capire da dove viene il N Log N. Capisco che, una volta assemblato l'octree, il calcolo delle forze è N log N perché devi passare attraverso ogni particella (N), e ogni particella "vede" approssimativamente il log N altre particelle a causa dell'ottre riduzione del numero di calcoli che deve essere eseguito per particelle distanti.

Ciò che sto ancora cercando di capire è quale sia la complessità per assemblare l'albero in primo luogo. È anche N log N? N perché devi farlo per ogni particella e logga N perché è approssimativamente quanto devi andare in profondità (con qualche fattore in primo piano) per raggiungere una foglia isolata nell'albero?

    
posta Joshua 01.12.2018 - 21:14
fonte

1 risposta

0

Sì, la creazione di un albero è in genere O (n log n). Ciò vale per tutti i tipi di alberi, indipendentemente dal numero di nodi figli per nodo, purché siano in qualche modo bilanciati. Ciò che cambia è la base del logaritmo, ad es. log 2 per un albero binario e log 8 per un octree - ma questa base può essere ignorata per la complessità asintotica.

Alcuni alberi usano le rotazioni dell'albero al momento dell'inserimento per mantenere l'equilibrio, oppure possiamo inserire nodi in un ordine che garantisce il bilanciamento (ad esempio ordinando tutti i nodi e combinandoli dal basso verso l'alto) o mescolando tutti i nodi in modo che vengano inseriti in un ordine casuale (spesso abbastanza buono nella pratica). Nota che l'ordinamento è anch'esso un'operazione O (n log n), quindi è fondamentalmente un'operazione gratuita quando si inserisce in un albero.

    
risposta data 01.12.2018 - 21:57
fonte

Leggi altre domande sui tag