如何提高这个js脚本的时间复杂度

Question

我快速编写了这段代码来测试长方体 a、b、c、d、e 和 f 的所有边和对角线是否均为整数。它似乎工作得很好，但循环越来越高的值需要太多时间（例如 10000+）。这是代码：

const generate_good_cuboid = () => {
  let good_couples = [];
  let couples = [];
  for (let a = 1; a < 10000; a++) {
    for (let b = 1; b < 10000; b++) {
      for (let c = 1; c < 10000; c++) {
        let e_squared = Math.pow(a, 2) + Math.pow(c, 2);
        let e = Math.sqrt(e_squared);
        if (Number.isInteger(e)) {
          let d_squared = Math.pow(a, 2) + Math.pow(b, 2);
          let d = Math.sqrt(d_squared);
          if (Number.isInteger(d)) {
            let f_squared = Math.pow(b, 2) + Math.pow(c, 2);
            let f = Math.sqrt(f_squared);
            if (Number.isInteger(f)) {
              good_couples.push({ a, b, c, d, e, f });
            }
          }
        }
      }
    }
  }

  return couples;
};

有什么方法可以让这段代码运行得更快吗？或者也许以某种方式摆脱那个令人讨厌的三个嵌套 for 循环？

我想了一些方法来降低这段代码的复杂性，但它并没有经历所有组合，这是我想要发生的事情。

Answer 1

如果 a 和 b 边没有给出整数，则可以避免内循环：

const generate_good_cuboid = sz => {
  let good_couples = [];
  for (let a = 1; a < sz; a++) {
    for (let b = 1; b < sz; b++) {
      const d = Math.sqrt(a**2 + b**2);
      if (Number.isInteger(d)) {
        for (let c = 1; c < sz; c++) {
          const e = Math.sqrt(a**2 + c**2);
          if (Number.isInteger(e)) {
            const f = Math.sqrt(b**2 + c**2);
            if (Number.isInteger(f)) {
              good_couples.push({ a, b, c, d, e, f });
            }
          }
        }
      }

    }
  }

  return good_couples;
};

console.log(generate_good_cuboid(10000));

Answer 2

一个简单的优化是计算

d

（从

a

和

b

）并在循环所有

c

之前检查其整数性。

此外，您可以通过将结果限制为

a=3, b=4

来避免生成重复项，例如

a=4, b=3

和

a < b < c

，并在需要所有解决方案时排列您的解决方案。然后你可以优化

for (let b = a; b < 10000; b++)

和

for (let c = b; c < 10000; c++)

（尽管这并没有真正改变复杂性）。

最后但并非最不重要的一点是，您可以预先生成所有已知良好的毕达哥拉斯三元组集（仅一次），然后搜索它们以找到共享一侧的两个三元组（三角形），并检查其他两条腿是否相同(catheti) 也构成勾股三元组。使用任何已知算法（https://en.wikipedia.org/wiki/Formulas_for_generate_Pythagorean_triples、https://en.wikipedia.org/wiki/Tree_of_primitive_Pythagorean_triples、https://codereview.stackexchange.com/ questions/250855/efficiently-find-all-the-pythagorean-triplets-where-all-numbers-less-than-1000，生成毕达哥拉斯三元组的最佳方法是什么？等）