这个毕达哥拉斯三重态函数的复杂度是多少？

Question

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(nnlogn)吗?

Answer 1

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

这个问题可以提供进一步的启发Time complexity of nested for-loop

这个毕达哥拉斯三重态函数的复杂度是多少？

What is the complexity of this pythagorean triplet function?

python

complexity-theory

pythagorean