是否有可能找到可以从长度列表中形成的三角形数量,而不是(n选择3)时间？

Question

这涉及到我正在研究的一个更大的问题.

例如,假设我们有一个列表

9 5 6 1

在可能的三角形将有长的边

(9,5,6)
(9,6,1)
(9,5,1)
(5,6,1)

有效的(由三角不等式)是

(9,5,6)
(5,6,1)

是否有可能在更好的O(n choose 3)时间内找到那些有效的？

Answer 1

一般情况下,答案是否定的:假设你得到了

 1, 1 - ?, 1 - 2 * ?, ..., 1 - (n - 1) * ? 

在这种情况下,所有3项的组合

 n * (n - 1) * (n - 2) / 6 = O(n**3)

是不同的,并制作有效的三角形,你O(n**3)只需枚举(和输出)它们的复杂性