畢達哥拉斯三元效率

我需要創建一個函數，它接受一個整數列表並返回列表中是否存在一個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

畢達哥拉斯三元效率

回答

相關問題