Comment trouver des triplets de pythagore dans un tableau plus vite que O(N^2)?
Quelqu'un peut-il suggérer un algorithme qui trouve tous les triplets de Pythagore parmi les nombres dans un tableau donné? Si c'est possible, s'il vous plaît, proposons un algorithme plus rapide que O(n2).
Triplet de pythagore est un ensemble {a,b,c} tels que a2 = b2 + c2. Exemple: pour le tableau [9, 2, 3, 4, 8, 5, 6, 10]
la sortie de l'algorithme doit être {3, 4, 5}
et {6, 8, 10}
.
- Qu'entendez-vous par "trouver des triplets de pythagore dans un tableau"? Êtes-vous commencer par un tableau d'entiers et d'essayer de trouver 3-l'élément de sous-ensembles que sont les triplets de Pythagore?
- veuillez reformuler la question et de la rendre plus claire
- la question n'est pas claire. peut-être, y compris un exemple de l'aide?
- Désolé pour l'ambiguïté de la question. Je vais vous expliquer avec un exemple. Supposons que j'ai un tableau comme { 9,2, 3, 4, 8, 5,6, 10} puis mon algorithme doit générer la sortie 3, 4, 5 et 6, 8, 10 en O(n) la complexité ou inférieure à 0(n2)
- Je sais que c'est un peu vieux mais si vous allez pour plus d'efficacité, vous pouvez organiser le tableau de haut en bas, et puis au moins réduire la liste vers le bas en veillant à ce que tous les candidats pour un est plus grand que b et c. De cette façon, si votre calculer chaque nombre avec des répétitions et vous avez 3 nombres dans un tableau, vous réduisez le nombre de chèques à partir de 27 à 2 :). Vous pouvez améliorer encore plus loin en ne permettant pas aux b et c du swap (Eg. b^2+c^2 = c^2+b^2), qui permettrait de réduire le nombre au-dessus de 1.
Vous devez vous connecter pour publier un commentaire.
Je comprends cette question
L'idée clé de la solution est la suivante:
Maintenant, vous savez comment résoudre ce type de tâche en moins de O(n2) le temps, utiliser un tel algorithme. Hors de mon esprit ne vient qu'à la suite de O(n2) solution:
Maintenant considérer chaque élément a[i]. Si a[i]=a[j]+a[k], alors, puisque les chiffres sont positifs et le tableau est maintenant triée, k<i et j<i.
De trouver de tels indices, exécuter une boucle qui augmente
j
de1
ài
, et diminuek
dei
à0
dans le même temps, jusqu'à ce qu'ils rencontrent. Augmentationj
sia[j]+a[k] < a[i]
, et de diminuerk
si la somme est plus grande quea[i]
. Si la somme est égale, c'est l'une des réponses, de l'imprimer, et de changer les deux indices.Cela prend O(i) des opérations.
i
. De cette façon, vous aurez besoin totalement O(n2) de l'exploitation, qui sera l'estimation finale.Personne ne sait comment faire nettement mieux que quadratique pour la étroitement liée 3SUM problème ( http://en.wikipedia.org/wiki/3SUM ). Je dirais que la possibilité d'une solution rapide à votre problème comme peu probable.
La 3SUM problème est de trouver a + b + c = 0. Laissez PYTHTRIP être le problème de trouver un^2 + b^2 = c^2 quand les entrées sont de vrais nombres algébriques. Voici le O(n log n)-réduction du temps de 3SUM à PYTHTRIP. Comme ShreevatsaR points, cela n'exclut pas la possibilité d'un certain nombre de la théorie des truc (ou une solution à 3SUM!).
- Nous d'abord de réduire 3SUM à un problème que je vais appeler 3SUM-ALT. Dans 3SUM-ALT, nous voulons trouver a + b = c, où tous les tableau entrées sont non négatifs. La finition de réduction à partir de 3SUM-ALT pour PYTHTRIP est juste de prendre des racines carrées.
Pour résoudre 3SUM à l'aide de 3SUM-ALT, d'abord éliminer la possibilité de triplets où l'un des a, b, c est zéro (O(n log n)). Maintenant, tout en satisfaisant triple dispose de deux nombres positifs et un négatif, ou deux négatif et un positif. Soit w un nombre supérieur à trois fois la valeur absolue de nombre d'entrée. Résoudre les deux instances de 3SUM-ALT: l'un où tout le négatif x sont mappés à des w - x et tout x positif sont mappés à 2w + x, où tous les x négatif sont mappés à 2 w - x et tout x positif sont mappés à w + x. Le reste de la preuve est simple.
a + b = c
(le problème de pythagore) être le même quea + b - c = 0
(équivalent à la 3SUM problème)?a+b=c
eta+b-c=0
sont évidemment les mêmes. Mais le problème de Pythagore n'est pasa+b=c
; il est: "étant donné un tableau de N entiers non négatifs, dire si elle contient (a,b,c) tels que a^2+b^2=c^2". Le 3SUM-ALT problème (preuve de l'équivalent de 3SUM ci-dessus) est "donné un tableau de N entiers non négatifs, dire si elle contient (a,b,c) tels que a+b=c". (Si vous le souhaitez, vous pouvez réécrire le PYTHTRIP comme "étant donné un tableau de N positif ou nul carré entiers, trouver (a,b,c) tels que a+b=c". Encore différent.)a+b=c
àa^2+b^2=c^2
rend ce différent), il faut noter le fait amusant que si nous changeons àa^3+b^3=c^3
(ou de toute puissance supérieure), alors le problème devient trivialement O(1): on peut répondre "Non" sans même regarder à l'entrée, par la le Dernier Théorème de Fermat. 🙂J'ai une autre solution,
Ne sais pas si c'est mieux mais vous pouvez les calculer en temps proportionnel à la valeur maximale dans la liste juste en informatique tout est possible triples inférieur ou égal à elle. Suivants du code Perl n'. La complexité temporelle de l'algorithme est proportionnelle à la valeur maximale de la somme des inverses des carrés 1 + 1/2^2 + 1/3^3 .... est égal à Pi^2/6, une constante.
J'ai simplement utilisé la formule de la Wikipédia page pour générer aucun uniques triples.
Voici une solution qui pourrait échelle de mieux pour les grandes listes de petits nombres. Au moins c'est différent ;v) .
Selon http://en.wikipedia.org/wiki/Pythagorean_triple#Generating_a_triple,
b
a l'air sympa, hein?b
, trouver la factorisation en nombres premiers. Naïvement à l'aide d'une table de nombres premiers inférieurs à la racine carrée de la plus grande valeur d'entrée M prendrait O(sqrt M/log M) le temps et l'espace* par élément.(m,n), m > n, b = 2mn
(saut bizarreb
), recherche pourm^2-n^2
etm^2+n^2
dans le tableau trié. O(log N) par paire, O(2^(Ω(M))) = O(log M)** paires par élément, O(N (log N) (log M)) total de l'.Analyse finale: O( N ( (sqrt M/log M) + (log N * log M) ) ), N = taille de la matrice, M = amplitude des valeurs.
(* Accepter 64-bits d'entrée, il y a environ 203M 32 bits, les nombres premiers, mais nous pouvons utiliser un tableau de différences au un octet par le premier, puisque les différences sont tous les même, et peut-être aussi de générer de grands nombres premiers dans l'ordre sur demande. Pour accepter de 32 bits d'entrée, d'une table de 16 bits les nombres premiers est nécessaire, ce qui est assez petit pour tenir dans le cache L1. Le temps ici est une surestimation en supposant que tous les facteurs premiers sont un peu moins de la racine carrée.)
(** Effectif lié inférieur en raison de la double facteurs premiers.)
a = d*(m^2 - n^2), b = d*2mn, c = d*(m^2 + n^2)
. Je ne suis pas sûr de ce que cela ferait de la complexité.(m,n), m > n, b = 2dmn
, et O(3^Ω(M))` de telles paires. Mais O(3^Ω(M)) = O(2^Ω(m)).Quelques-uns de mes collègues ont demandé à ce même problème dans une java cert sûr, ils ont pris la solution que nous avons fait était de O(N^2). Nous rasée la plus grande partie de l'espace du problème que nous le pouvions, mais nous ne pouvions pas trouver un moyen de chute de la complexité de N Log N ou mieux.
Solution en O(N).
m^2+1= max .... mettre max à partir de l'étape 2. trouver m dans cette équation.O(1)
choisir étage de min de (étapes 4,5,6) disons minValue.O(1)
choisir ceil de max de (étapes 4,5,6) disons maxValue.O(1)
boucle à partir de j=minValue à maxValue. maxvalue-minvalue sera inférieur à la racine de N.
9.le fait de calculer trois numéros de j^2-1,2 j,j^2+1.
9.b recherche de ces numéros de table de hachage. si trouvé revenir réussite.
Si (a, b, c) est un Pythagoricien triple, alors il en est (ka, kb, kc) pour tout entier positif.
donc il suffit de trouver une valeur pour a, b, et c, et ensuite, vous pouvez calculer autant de nouvelles que vous le souhaitez.
Pseudo-code:
Laissez-moi savoir si ce n'est pas exactement ce que vous cherchez.
Il peut être fait en O(n) fois. première de hachage les éléments de la carte pour vérifier l'existence. après cela, appliquer l'algorithme ci-dessous
Balayage de la matrice et si l'élément est le même nombre, (n,n^2/2 +1, n^2/2 -1) est le triplet être trouvé. il suffit de cocher pour que l'existence de l'aide de hachage carte de recherche. si tous les éléments du triplet existe, imprimer le triplet.
C'est celui que j'avais mis en œuvre ...
Voici la mise en œuvre en Java:
si le problème est celui "Pour un Tableau d'entiers trouver tous les triplets tels que a^2+b^2 = c^2
Trier le tableau dans l'ordre croissant
Trois pointeurs p1,p2,p3, à des entrées de 0,1,2
ensemble pEnd au-delà de la dernière entrée dans le tableau
tandis que (p2 < pend-2)
{
}
il se déplace à 3 points de la matrice de sorte qu'il O(tri(n) + n)
ce n'est pas n2 parce que le passage suivant commence au plus grand nombre et n'est pas réinitialisé.
si le dernier était trop petit pour le triple, c'est toujours pour les petits, quand vous allez à la prochaine plus grande a et b
Trouver des triplets de Pythagore en O(n)
Algorithme:
Répéter jusqu'à la fin du tableau est atteint
Complexité: O(n)