1 
def tuplePyth(n):
    list_=[]
    for x in range(1, n):
        for y in range(x + 1, (n - x) // 2):
            for z in range (y + 1, n - x - y):
               if smallestTrip(x, y, z)==False:
                    list_.append([x,y,z])
    print (list_)

def pythTrue(a,b,c):
    (A,B,C) = (a*a,b*b,c*c)
    if A + B == C or B + C == A or A + C == B:
        return True

def smallestTrip(a,b,c):
    if pythTrue(a,b,c) == True:
        if (a+b+c)%12 == 0:
            return True
        else:
            return False

smallestTrip检查 x,y,z 是否是基本 3,4,5 直角三角形的倍数。

目标是生成所有可能的毕达哥拉斯三元组，其总和小于输入的总和 n。

（这些三元组不能是 (3,4,5) 三角形的倍数。）

这里的复杂度是 O(n n logn) 吗？

4

1 回答 1

2

n其他函数是 O(1) 并且您在原始问题中有三个循环。所以复杂度是 O(n * n * n) = O(n^3)

这个问题可能会提供进一步的说明嵌套for循环的时间复杂度

于 2018-11-04T15:42:01.413 回答