Wydajna metoda sprowadzania jak ocena sumy - algorytm, fft, geometria obliczeniowa, splot, wyrazy matematyczne

Problem Biorąc pod uwagę N trójwymiarowych punktów, które są {$ p_1, p_2, .., p_n $} gdzie $ p_i = (x_i, y_i, z_i) $. Muszę znaleźć wartość formuły

dla niektórych podanych stałych liczb całkowitych P, Q, R, S. wszystkie liczby są między 1 a M (= 100).

Potrzebuję skutecznej metody obliczania tej formuły

Proszę podać jakiś pomysł, jak zmniejszyć złożoność lepiej niż $ O (n ^ 2) $

Odpowiedzi:

Zakładając, że wszystkie współrzędne wynoszą od 1 do 100, można to zrobić za pomocą:

1. Oblicz 3d histogram wszystkich operacji O (100 * 100 * 100).

2. Użyj FFT, aby obliczyć splot histogramów wzdłuż każdej z 3 osi

Spowoduje to powstanie histogramu 3d wektorów 3D. Następnie można iterować po tym histogramie, aby obliczyć żądaną wartość.

Najważniejsze jest to, że obliczenie splotuhistogram wartości oblicza histogram różnic par tych wartości. Można to również wykorzystać do obliczenia histogramu sum wartości w podobny sposób.

Twój problem wygląda jak problem z potencjalnymi cząstkami (na przykład w elektrodynamice), w którym musisz znaleźć „potencjał” w lokalizacji (x_j, y_j) sumując wszystkie podstawowe składki z i-th cząsteczki.

Szybki algorytm specyficzny dla tej klasyproblemy to szybka metoda Multipole. Wyszukaj to słowo kluczowe, ale muszę cię ostrzec, że nie jest to łatwe do zrozumienia lub wdrożenia. Potrzebne jest silne tło matematyczne.