Общее количество возможных треугольников из n чисел
Если даны n чисел, как мне найти общее количество возможных треугольников? Есть ли какой-либо метод, который сделает это менее чем за O (n ^ 3) время?
Я рассматриваю a + b> c , b + c> a и a + c> b условия для того, чтобы быть треугольником.
23
задан Bill the Lizard 19 September 2012 в 22:04
поделиться
2 ответа
Хотя мы можем использовать бинарный поиск, чтобы найти значение «k», следовательно, улучшить временную сложность!
1
ответ дан 29 November 2019 в 01:08
поделиться
Кажется, нет лучшего алгоритма, чем O (n ^ 3). В худшем случае сам набор результатов содержит O (n ^ 3) элементов.
Например, если задано n равных чисел, алгоритм должен вернуть n * (n-1) * (n-2) результатов.
-1
ответ дан 29 November 2019 в 01:08
поделиться
Другие вопросы по тегам: