Доказательство: Пифагорейский тройной алгоритм быстрее по формуле Евклида?

Question

Как назначение класса, я должен написать программу на C, чтобы сгенерировать все пифагорейские троек ниже заданного значения 't'. Вот мой код, который сначала генерирует примитивный триплет (a, b, c) с использованием Euclid's Formula и печатает все триплеты формы (ka, kb, kc) для 1 < kc < t.

for (i = 2; i < (sqrt(t) + 1); i++) 
    for (j = 1; j < i; j++) 
     if ((gcd(i,j) == 1) && ((i-j) % 2) && ((i*i + j*j) < t)) 
     { 
      k = 0; 
      a = i * i - j * j; 
      b = 2 * i * j; 
      c = i * i + j * j; 

      while ((++k) * c < t) 
       printf("(%d, %d, %d)\n", k*a, k*b, k*c); 
     } 

Большинство других алгоритмов, которые я наткнулся на использование вложенных циклов, чтобы проверить сумму квадратов, и значительно медленнее, чем это, как т растет. Можно ли вывести доказательство, что оно действительно быстрее?

Answer 1

Algorithm complexity - общий метод анализа алгоритмической производительности. В частности, big O обычно используется для сравнения алгоритмов, основанных на худшем случае каждого из них.

В Вас случае, если вы имеете 4 петли:

• for, что итерация тщательное i
• for, что итерация тщательное j
• Цикл внутри gcd
• while петли

В худшем случае каждая из этих циклов выполняет итерации sqrt(t). Большая сложность O была бы такой:

O(for_i) * O(for_j) * (O(gcd) + O(while)) 
= 
O(sqrt(t)) * O(sqrt(t)) * (O(sqrt(t)) + O(sqrt(t))) 
= 
O(t*sqrt(t)) 

Для других алгоритмов, которые медленнее, чем ваш метод. Вы можете применить одну и ту же аргументацию, чтобы найти свой большой O, а затем показать, что этот большой O больше, чем ваш. Например, наивный алгоритм, который проверяет все суммы квадратов, будет иметь 2 вложенных цикла; каждый имеет не более t итераций, и поэтому большой O - это O(t*t) > O(t*sqrt(t)).

Answer 2

В качестве альтернативы алгоритму Евклида, если (a, b, c) является примитивной пифагорейской тройкой, то есть (a-2b + 2c, 2a-b + 2c, 2a-2b + 3c), (a + 2b + 2c, 2a + b + 2c, 2a + 2b + 3c) и (-a + 2b + 2c, -2a + b + 2c, -2a + 2b + 3c). Вот алгоритм в Python (потому что я только что произошло, чтобы алгоритм в Python, и я слишком ленив, чтобы переписать его в C, и в любом случае, это ваше домашнее задание):

def pyth(n): 
    def p(a, b, c): 
     if n < a + b + c: return [] 
     return ([[a, b, c]] if a < b else [[b, a, c]]) \ 
      + p(a-b-b+c+c, a+a-b+c+c, a+a-b-b+c+c+c) \ 
      + p(a+b+b+c+c, a+a+b+c+c, a+a+b+b+c+c+c) \ 
      + p(c+c+b+b-a, c+c+b-a-a, c+c+c+b+b-a-a) 
    return p(3, 4, 5) 

Тогда легко умножить каждый примитивный треугольник с помощью последовательных констант, пока вы не достигнете предела. Я не уверен, что это быстрее, чем алгоритм Евклида, но я надеюсь, что это потому, что он не имеет вычислений gcd.