Generalised 3SUM (k-SUM) problem?

29

Le problème 3SUM essaie d'identifier 3 entiersune,b,cSnune+b+c=0

On suppose qu'il n'y a pas de meilleure solution que quadratique, c'est-à-dire o(n2)o(nbûche(n)+n2)

Je me demandais donc si cela s'appliquerait au problème généralisé: trouver des entiers unejeje[1..k]Snje[1..k]uneje=0

I think you can do this in o(nbûche(n)+nk-1)k2k=3
k

bitmask
la source
article / article récent sur 3SUM qui examine les limites inférieures de la complexité de son arbre de décision
vzn

Réponses:

27

k

  • Même pour kSk/2SX-XO(nk/2bûchen)

  • Pour impair kS(k-1)/2uneSX-une-XXO(n2)O(n(k+1)/2)

Les deux algorithmes sont optimaux (sauf éventuellement pour le facteur logarithmique lorsque k2k

JeffE
la source
stackoverflow.com/a/14737071/511736 suggère l'algorithme O (n ^ 2) lorsque k = 4
Kowser
1
Le hachage, c'est de la triche. L'algorithme décrit dans StackOverflow ne s'exécute qu'en O (n ^ 2) pour une entrée entière, et uniquement avec une probabilité élevée, et uniquement si vous utilisez une fonction de hachage aléatoire appropriée. Les algorithmes de ma réponse fonctionnent dans le modèle réel de RAM, ils sont complètement déterministes et les limites de temps sont les pires des cas. Vous pouvez également raser les facteurs de journalisation dans le paramètre entier à l'aide de "trucs de bits", mais c'est un peu ennuyeux.
JeffE
12

-SUM nécessite du temps nΩ() sauf si k-SAT peut être résolu en 2o(n)temps pour toute constante k. Cela a été montré dans un article de Mihai Patrascu et Ryan Williams (1).

En d'autres termes, en supposant l' hypothèse de temps exponentielle , votre algorithme est optimal jusqu'à un facteur constant dans l'exposant (un facteur polynomial dansn)

(1) Mihai Patrascu et Ryan Williams. Sur la possibilité d'algorithmes SAT plus rapides. Proc. 21e Symposium ACM / SIAM sur les algorithmes discrets (SODA2010)

SamM
la source
3

Voici quelques observations simples.

Pour k=1, vous pouvez le faire en Θ(n)temps en balayant le tableau pour un zéro. Pourk=2, vous pouvez le faire sans hachage Θ(nbûchen)temps. Triez la baie puis scannez-la. Pour chaque élémentje faire une recherche binaire pour -je. Il en résulte une complexité totale deΘ(nbûchen). Pour le cask=n vous pouvez le faire en Θ(n) temps en accumulant le tableau et en vérifiant le résultat.

Pour plus de références, consultez la page du projet Problèmes ouverts pour 3SUM .

Juho
la source
-1

Voir http://arxiv.org/abs/1407.4640

Un nouvel algorithme pour résoudre le problème rSUM Valerii Sopin

Abstrait:

Un algorithme déterminé est présenté pour résoudre le problème rSUM pour tout r naturel avec une évaluation sub-quadratique de la complexité temporelle dans certains cas. En termes de quantité de mémoire utilisée, l'algorithme obtenu a également un ordre sub-quadratique. L'idée de l'algorithme obtenu est basée non pas sur les nombres entiers, mais sur k∈N bits successifs de ces nombres dans le système de numération binaire. On montre que si une somme de nombres entiers est égale à zéro, alors la somme de nombres présentée par tout k bits successifs de ces nombres doit être suffisamment "proche" de zéro. Cela permet d'écarter les chiffres qui, a fortiori, n'établissent pas la solution.

C'est quelque chose de nouveau dans ce numéro.

user20970
la source
1
Pourriez-vous citer explicitement les résultats de l'article qui sont pertinents pour la question? (Coller le résumé peut être correct, si l'article est pertinent dans son ensemble.) Les messages sur SE sont censés être plus qu'un simple lien.
FrankW
1
En l'état, cette réponse est un commentaire (potentiellement utile), pas une réponse. En tant que tel, il devrait contenir du contenu original, par exemple votre description de l'algorithme dans vos propres mots. Veux-tu le faire? Je peux convertir votre réponse en commentaire si vous ne le faites pas. (Je suis conscient que vous ne pouvez pas commenter à cause de votre représentant.)
Raphael
Cela ne ressemble pas à un document crédible. L'affirmation "complexité temporelle sub-quadratique dans certains cas" n'est pas une déclaration utile. La complexité temporelle est par définition la durée d'exécution la plus défavorable. Le tri à bulles s'exécute en temps linéaire dans certains cas, mais sa complexité temporelle reste quadratique.
DW