Задача Для N трехмерных точек, которые являются {$ p_1, p_2, .., p_n $}, где $ p_i = (x_i, y_i, z_i) $. Я должен найти значение формулыЭффективный метод свертки, такой как оценка суммы
для некоторых заданных постоянных целых чисел P, Q, R, S. все числа от 1 до М (= 100).
мне нужен эффективный метод расчета по этой формуле
Пожалуйста, дайте какие-либо идеи о том, как уменьшить сложность лучше, чем $ O (N^2) $
Если предположить, что все координаты находятся между 1 и 100, то вы могли бы это сделать через:
Вычислить трехмерную гистограмму всех точек O (100 * 100 * 100) операций.
Использование БПФ для вычисления свертки гистограмм вдоль каждой из осей 3
Это приведет в 3D гистограммы 3d векторов. Затем вы можете перебрать эту гистограмму для вычисления желаемого значения.
Главное, что вычисление свертки гистограммы значений вычисляет гистограмму парных различий этих значений. Это также можно использовать для вычисления гистограммы сумм значений аналогичным образом.
Можете ли вы объяснить это немного больше, пожалуйста. т. е. как вычислить трехмерную гистограмму, а затем свертки. Возможно, дайте некоторые ссылки для этого – v78
. Пример учебника и кода для выполнения сверток с fft доступен на [codechef] (https://discuss.codechef.com/questions/18331/farasa-editorial) –
Можете ли вы рассказать мне больше о трехмерной гистограмме. – v78
Ваша проблема выглядит как проблема с потенциалом частиц (например, у вас в электродинамике), где вам нужно найти «потенциал» в местоположении (x_j, y_j), суммируя все элементарные вклады от частиц i-th.
Быстрый алгоритм, специфичный для этого класса проблем, - метод Fast Multipole. Посмотрите это ключевое слово, но я должен предупредить вас, что это никоим образом не просто понять или реализовать. Необходим сильный математический фон.
Что такое 'P, Q, R, S' и их выражения как' Q (Yi-Yj) 'должно быть? – RBarryYoung
Алос, как это связано с БПФ и сверткой? – RBarryYoung
Извините за путаницу, Q (Yi-Yj) является произведением Q и (Yi-Yj) и теперь исправлено. – v78