证明:毕达哥拉斯三重算法由欧几里德公式更快？

Question

作为课堂作业,我要编写一个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的增长而明显慢于此.是否有可能推断出它确实更快的证据？

Answer 1

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