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?