Можно ли найти количество треугольников, которые могут быть сформированы из списка длин лучше, чем (n выбирают 3) времени?

Это относится к большей проблеме, над которой я работаю.

Например, скажем, нам предоставлен список

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) времени?

Ответ 1

В общем случае ответ отрицательный: представьте, что вам дано

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

В этом случае все комбинации из 3 элементов

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

являются четкими и делают правильные треугольники, и у вас есть сложность O(n**3) просто для перечисления (и вывода) их

Ответ 2

Сначала отсортируйте свой список.

Теперь вместо выполнения полного поиска O (n ^ 3) нам нужно только найти пару точек в O (n ^ 2) и найти третью точку (возможно, более одной точки, поэтому вам нужно проверить нижняя граница и верхняя граница), выполняя двоичный поиск.

Таким образом, в целом новая сложность O (n ^ 2 log (n))

Ответ 3

Нет. У вас может быть произвольно большой набор входов, где каждая тройка является допустимым треугольником.