Comment trouver des triplets pythagoriciens dans un tableau plus rapidement que O (N ^ 2)?

Question

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, veuillez suggérer un algorithme plus rapide que O (n ² ).

Le triplet de Pythagore est un ensemble {a, b, c} tel que a ² = b ² + c ² . 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} .

Answer 1

Je comprends cette question

Étant donné un tableau, trouver tous ces triplets i,j et k, tel que a[i]² = a[j]²+[k]²

L'idée clé de la solution est:

• Place de chaque élément. (Cela prend O(n) le temps). Cela permettra de réduire la tâche d'origine afin de "trouver trois nombres dans le tableau, dont l'un est la somme des deux autres".

Maintenant, vous savez comment résoudre ce type de tâche en moins de O(n²) temps, utiliser un tel algorithme. Hors de mon esprit ne vient qu'à la suite de O(n²) solution:

1. Trier le tableau dans l'ordre croissant. Cela prend un temps O(n log n).

2. 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.

   Pour trouver de tels indices, exécuter une boucle qui augmente j de 1 de i, et diminue k de i de 0 dans le même temps, jusqu'à ce qu'ils rencontrent. Augmentation j si a[j]+a[k] < a[i], et de diminuer k si la somme est supérieure à l' a[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.

3. Répétez l'étape 2 pour chaque indice i. De cette façon, vous aurez besoin totalement O(n²) opérations, qui sera l'estimation finale.

Answer 2

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.

---

Le 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 avons d'abord 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.

Answer 3

J'ai encore une solution,

 //sort the array in ascending order 
//find the square of each element in the array

//let 'a' be the array containing square of each element in ascending order 

for(i->0 to (a.length-1))
  for (j->i+1 to  (a.length-1))
    //search the a[i]+a[j] ahead in the array from j+1 to the end of array
      //if found get the triplet according to sqrt(a[i]),sqrt(a[j]) & sqrt(a[i]+a[j])
  endfor
endfor
 

Answer 4

Vous ne savez 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.

my $list = [9, 2, 3, 4, 8, 5, 6, 10];
pythagoreanTriplets ($list);

sub pythagoreanTriplets
{
  my $list = $_[0];
  my %hash;
  my $max = 0;
  foreach my $value (@$list)
  {
    $hash{$value} = 1;
    $max = $value if ($value > $max);
  }
  my $sqrtMax = 1 + int sqrt $max;

  for (my $n = 1; $n <= $sqrtMax; $n++)
  {
    my $n2 = $n * $n;
    for (my $m = $n + 1; $m <= $sqrtMax; $m++)
    {
      my $m2 = $m * $m;
      my $maxK = 1 + int ($max / ($m2 + $n2));
      for (my $k = 1; $k <= $maxK; $k++)
      {
        my $a = $k * ($m2 - $n2);
        my $b = $k * (2 * $m * $n);
        my $c = $k * ($m2 + $n2);
        print "$a $b $c\n" if (exists ($hash{$a}) && exists ($hash{$b}) && exists ($hash{$c}));
      }
    }
  }
}

Answer 5

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,

a = m^2 - n^2, b = 2mn, c = m^2 + n^2 

b a l'air sympa, hein?

• Trier le tableau en O(N log N) en temps.
• Pour chaque élément, 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) l'espace et le temps* par élément.
• Pour chaque paire, (m,n), m > n, b = 2mn (sauter étrange b), recherche d' m^2-n^2 et m^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.

(* Pour 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 à 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.)