5

作为课堂作业，我将编写一个 C 程序来生成所有低于给定值 't' 的毕达哥拉斯三元组。这是我的代码，它首先使用欧几里得公式生成一个原始三元组 (a, b, c) ，然后打印所有形式为 (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);
        }

我遇到的大多数其他算法都使用嵌套循环来检查平方和，并且随着 t 的增长比这慢得多。是否可以推断出它确实更快的证据？

4

2 回答 2

3

算法复杂度是分析算法性能的通用方法。特别是，大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)).

于 2013-08-18T01:26:11.337 回答
1

As an alternative to Euclid's algorithm, if (a, b, c) is a primitive pythagorean triple, so are (a-2b+2c, 2a-b+2c, 2a-2b+3c), (a+2b+2c, 2a+b+2c, 2a+2b+3c) and (-a+2b+2c, -2a+b+2c, -2a+2b+3c). Here's the algorithm in Python (because I just happened to have the algorithm in Python, and I'm too lazy to rewrite it in C, and anyway, it's your homework):

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)

Then it is easy to multiply each primitive triangle by successive constants until you reach the limit. I'm not sure if this is faster than Euclid's algorithm, but I'm hopeful that it is because it has no gcd calculations.

于 2013-08-18T11:54:22.863 回答