Paires d'un ensemble dense: Déterminer l'histogramme des sommes beaucoup plus rapidement que (n²) - algorithme, combinatoire

Étant donné un ensemble S de n nombres naturels inférieurs à 9n/ 7, comment peut-on établir le nombre de paires totalisant chaque nombre de 0 à 18n/sept? (2 combinaisons, 3 < n)
Laisser m être la valeur maximale des éléments dans S.
Si m était n-1, la suite des comptes de paires dont le total est égal à (0, 1,… 18n/ 7) serait [0, 1, 1, 2, 2,… m / 2, m / 2, (m+2) / 2, m / 2, m / 2, (m-2) / 2,… 2, 1, 1, 1, 0,…, 0] pour impair nou [0, 1, 1, 2,… (n-2) / 2, (n-2) / 2, n/ 2, n/ 2, n/ 2, (n-2) / 2, (n-2) / 2, (n-4) / 2,… 2, 1, 1, 0,…, 0] pour un même n.
Il n’est pas trop difficile d’établir les comptes si n est un élément de S (et l'un des nombres ci-dessous n'est pas "t"), tout comme l'imbrication de deux boucles et le simple comptage des occurrences de chaque somme - Ο (n²):

Comment établir un histogramme des sommes des paires (beaucoup) plus rapide que Ο (n²)?
(Est-ce que savoir m <9n/ 7 aide?
Est-ce notamment plus difficile pour 9n/ 2 < m (ensemble (semi-) clairsemé)?)

Réponses:

Cela peut être fait en O(nlogn), utilisant la transformation de Fourier.

Rappelons d'abord qu'un convolution est défini comme:

(h*g)[n] = sum { h[n-i] + f[i] | i in Z }

Et notez qu'une convolution sur la histogramme des données est exactement ce que vous voulez. La convolution peut être calculée en O(nlogn) en utilisant Transformée de Fourier.

Cela donne l'algorithme de base suivant:

1. Créez un histogramme avec une carte basée sur has / tree. Que ce soit h.
2. en utilisant une transformée de Fourier pour trouver (h * h).