Трудно представить N чисел (где N умеренно велико), чтобы треугольника не было.Но мы попробуем:
Рассмотрим растущую последовательность, где каждое следующее значение находится на пределе N[i] = N[i-1] + N[i-2].Это не что иное, как последовательность Фибоначчи.Приблизительно это можно рассматривать как геометрическую прогрессию с коэффициентом золотого сечения (GRf ~ = 1.618).
Можно видеть, что если N_largest < N_smallest * (GRf**(N-1)), то обязательно будет треугольный триплет.Это определение является довольно нечетким из-за числа с плавающей точкой в сравнении с целым числом и из-за GRf, это предел, а не фактический геометрический фактор.В любом случае, тщательно выполненный тест даст тест O (n), который может проверить, есть ли триплет.Если нет, то мы должны выполнить некоторые другие тесты (все еще размышляя).
EDIT : Прямой вывод из идеи Фибоначчи состоит в том, что для целочисленного ввода (как указано в Q) будут существоватьгарантированное решение для любого возможного ввода , если размер массива будет больше, чем log_GRf(MAX_INT), а это 47 для 32 бит или 93 для 64 бит.На самом деле, мы можем использовать наибольшее значение из входного массива, чтобы определить его лучше.
Это дает нам следующий алгоритм:
Шаг 1) Найти MAX_VAL из входных данных: O(n)
Шаг 2) Вычислить минимальный размер массива, который гарантировал бы существованиерешения:
N_LIMIT = log_base_GRf(MAX_VAL): O(1)
Шаг 3.1), если N> N_LIMIT: вернуть true: O(1)
Шаг 3.2), иначе сортировать и использовать прямыеМетод O(n*log(n))
Поскольку для больших значений N (и это единственный случай, когда сложность имеет значение), это O(n) (или даже O(1) в случаях, когда N > log_base_GRf(MAX_INT)), мы можем сказать, что этоO(n).