Какова сложность этой трифлетной функции Пифагора? - PullRequest
Новая
       13

Какова сложность этой трифлетной функции Пифагора?

0 голосов
/ 04 ноября 2018 
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)?

1 Ответ

0 голосов
/ 04 ноября 2018

Другими функциями являются O (1), и у вас есть три цикла относительно n в исходной задаче. Таким образом, сложность O (n * n * n) = O (n ^ 3)

Этот вопрос может обеспечить дополнительное освещение Временная сложность вложенного цикла for

...