毕达哥拉斯三元效率

我需要创建一个函数，它接受一个整数列表并返回列表中是否存在一个Pythagorean三元组。例如，[3, 5, 7, 4]返回True，因为3,4,5是毕达哥拉斯三元组。到目前为止，我有这个（在Python中）：毕达哥拉斯三元效率

def containsPythagoreanTriple(a): 
    for i in xrange(len(a)): #square the numbers 
     num = a[i] 
     a[i] = num**2 
    a = sorted(a) 
    for start in xrange(len(a)): #compare every pair 
     for i in xrange(start+1, len(a)): 
      if a[start] + a[i] in a: 
       return True 
    return False

有没有办法让这更有效？

来源

2014-10-05 sammuh

就性能而言，该代码中有一些可以改进的地方。

当前的实现是O(N**3)（其中N是len(a)），你是否平方的列表包含对每个项目的每个总和。 list中的成员资格测试是O(N)，并且有O(N**2)对要测试。

您可以通过使用set而不是列表来保存您的项目来改善此位。在set中测试项目成员资格是O(1)，所以您将以这种方式获得O(N**2)算法。

还有一些进一步的变化可能会加速一些事情，但没有一个能够进一步改变渐近复杂性。首先，您无需致电sorted，因为无论如何您都要测试每一对物品。你也可以使用一组理解来做你的平方，而不是覆盖原来的a列表。最后，您可以使用itertools.combinations来生成您的正方形对，并在生成器表达式上使用any来测试它们的总和是否在集合中。

下面是使用相同的算法一些优化代码：

import itertools 

def containsPythagoreanTriple(a): 
    squares = {x*x for x in a} # set comprehension 
    return any(x+y in squares for x,y in itertools.combinations(squares))

有可能仍然是空间进一步优化的东西多一点，在更基本的方式改变算法。例如，你不需要测试每一对，因为有些值永远不会是三角形的“短腿”（例如最大值）。您可以过滤传递至itertools.combinations的方块，使其仅包含小于或等于max(squares)-min(squares)的方块。我不确定这是否值得，除非你的值列表变得非常大。

来源

2014-10-05 20:19:22 Blckknght

相同，但略有不同

import math  
def tripple(array): 
    array = sorted(array) 
    for start in xrange(len(array)): #compare every pair 
     m = array[start] 
     for i in xrange(start+1, len(array)): 
     n = array[i] 
     if math.sqrt(n*n+m*m) in array: 
      print m, n, math.sqrt(n*n+m*m) 

array=[4, 6, 2, 3, 7, 5, 9, 8, 10, 12, 15, 40, 41];  
tripple(array);

来源

2014-10-05 20:27:36 user3883456

毕达哥拉斯三元效率

回答

相关问题