证明：毕达哥拉斯三重算法用欧几里得公式更快？

Question

作为一个类任务，我将编写一个C程序来生成所有低于给定值not'的毕达哥拉斯三元组。下面是我的代码，它首先使用欧几里德公式生成一个原语三元组(a，b，c)，并打印形式为1

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个循环：

• 彻底迭代i
的 用于的
• 的迭代彻底J
• gcd
内的循环
• while循环

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))