Это относится к большей проблеме, над которой я работаю.
Например, скажем, нам предоставлен список
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 - 2 * ε, ..., 1 - (n - 1) * ε
В этом случае все комбинации из 3 элементов
n * (n - 1) * (n - 2) / 6 = O(n**3)
являются четкими и делают правильные треугольники, и у вас есть сложность O(n**3) просто для перечисления (и вывода) их
Сначала отсортируйте свой список.
Теперь вместо выполнения полного поиска O (n ^ 3) нам нужно только найти пару точек в O (n ^ 2) и найти третью точку (возможно, более одной точки, поэтому вам нужно проверить нижняя граница и верхняя граница), выполняя двоичный поиск.
Таким образом, в целом новая сложность O (n ^ 2 log (n))
Нет. У вас может быть произвольно большой набор входов, где каждая тройка является допустимым треугольником.