Общее количество возможных треугольников из n чисел

Question

Если дано n чисел, как мне найти общее количество возможных треугольников? Есть ли метод, который делает это менее чем за O(n^3) время?

Я рассматриваю a+b>c, b+c>a и a+c>b условия для того, чтобы быть треугольником.

Answer 1

Предположим, что в данном n нет равных чисел, и разрешено использовать одно число более одного раза.Например, мы дали числа {1,2,3}, чтобы мы могли создать 7 треугольников:

1. 1 1 1
2. 1 2 2
3. 13 3
4. 2 2 2
5. 2 2 3
6. 2 3 3
7. 3 3 3

Если какое-либо из этих предположений неверно, алгоритм легко изменить.

Здесь я представляю алгоритм, который в худшем случае занимает время O (n ^ 2):

1. Сортировка номеров (в порядке возрастания).Мы возьмем тройки ai <= aj <= ak, так что i <= j <= k. </li>
2. Для каждого i, j вам нужно найти наибольшее k, удовлетворяющее ak <= ai + aj.Тогда все тройки (ai, aj, al) j <= l <= k - треугольник (поскольку ak> = aj> = ai мы можем нарушать только ak

Рассмотрим две пары (i, j1) и (i, j2) j1 <= j2.Легко видеть, что k2 (найдено на шаге 2 для (i, j2))> = k1 (найдено один шаг 2 для (i, j1)).Это означает, что если вы выполняете итерацию для j, и вам нужно только проверять числа, начиная с предыдущего k.Таким образом, он дает вам O (n) сложность времени для каждого конкретного i, что подразумевает O (n ^ 2) для всего алгоритма.

Исходный код C ++:

int Solve(int* a, int n)
{
    int answer = 0;
    std::sort(a, a + n);

    for (int i = 0; i < n; ++i)
    {
        int k = i;

        for (int j = i; j < n; ++j)
        {
            while (n > k && a[i] + a[j] > a[k])
                ++k;

            answer += k - j;
        }
    }

    return answer;
}

Обновление для downvoters:

Это определенно O (n ^ 2)!Пожалуйста, внимательно прочитайте «Введение в алгоритмы» главы Томаса Х. Кормена об амортизированном анализе (17.2 во втором издании). Находить сложность путем подсчета вложенных циклов иногда совершенно неправильно. Здесь я пытаюсь объяснить это настолько просто, насколько смогу.Давайте исправим переменную i .Затем для этого i мы должны выполнить итерацию j с i до n (это означает операцию O (n)) и внутреннюю итерацию цикла k от i до n (это также означает операцию O (n)). Примечание: я не запускаю цикл с начала для каждого j .Нам также нужно сделать это для каждого i от 0 до n .Таким образом, это дает нам n * (O (n) + O (n)) = O (n ^ 2) .

Answer 2

В O(n^2*logn).

есть простой алгоритм.

• Предположим, вы хотите, чтобы все треугольники были тройками (a, b, c), где a <= b <= c.
• Существует 3 неравенства треугольника, но достаточно только a + b > c (другие тогда выполняются тривиально).

А теперь:

• Сортировать последовательность по O(n * logn), например, по сортировке слиянием.
• Для каждой пары (a, b), a <= b оставшееся значение c должно быть не менее b и меньше a + b.
• Так что вам нужно посчитать количество предметов в интервале [b, a+b).

Это можно сделать, просто выполнив двоичный поиск a + b (O(logn)) и посчитав количество элементов в [b,a+b) для каждой возможности, которая является b-a.

Все вместе O(n * logn + n^2 * logn), что O(n^2 * logn). Надеюсь, это поможет.

Answer 3

Если вы используете двоичную сортировку, это O (n-log (n)), верно?Держите ваше двоичное дерево под рукой, и для каждой пары (a, b), где ab и c <(a + b). </p>

Answer 4

Пусть a, b и c - три стороны. Приведенное ниже условие должно выполняться для треугольника (сумма двух сторон больше третьей стороны)

i) a + b > c
ii) b + c > a
iii) a + c > b

Ниже приведены шаги для подсчета треугольника.

1. Сортировка массива в порядке убывания.

2. Инициализируйте два указателя «i» и «j» на первый и второй элементы соответственно и инициализируйте число треугольников как 0.

3. Исправьте 'i' и 'j' и найдите самый правый индекс 'k' (или самый большой 'arr [k]'), такой что 'arr [i] + arr [j]> arr [k]' , Число треугольников, которые могут быть сформированы с помощью ‘arr [i]‘ и ‘arr [j]‘ в качестве двух сторон, равно ‘k - j’. Добавьте ‘k - j’ к числу треугольников.

Давайте рассмотрим ‘arr [i]‘ как ‘,‘ arr [j] ‘как b и все элементы между‘ arr [j + 1] ‘и‘ arr [k] ‘как‘ c ’. Вышеупомянутые условия (ii) и (iii) выполняются, потому что ‘arr [i]

4. Инкремент ‘j’, чтобы снова исправить второй элемент.

Обратите внимание, что на шаге 3 мы можем использовать предыдущее значение ‘k’. Причина проста: если мы знаем, что значение «arr [i] + arr [j-1]» больше, чем «arr [k]», то мы можем сказать «arr [i] + arr [j]» также будет больше, чем 'arr [k]', поскольку массив отсортирован в порядке возрастания.

5.Если «j» достигло конца, затем увеличьте «i». Инициализируйте «j» как «i + 1», «k» как «i + 2» и повторите шаги 3 и 4.

Сложность времени: O (n ^ 2). Сложность по времени выглядит больше из-за 3-х вложенных циклов. Если мы поближе познакомимся с алгоритмом, то заметим, что k инициализируется только один раз во внешнем цикле. Самый внутренний цикл выполняется не более O (n) времени для каждой итерации самого внешнего цикла, потому что k начинается с i + 2 и повышается до n для всех значений j. Следовательно, сложность времени составляет O (n ^ 2).

Answer 5

возможный ответ

Хотя мы можем использовать двоичный поиск, чтобы найти значение 'k', следовательно, улучшить временную сложность!

Answer 6

Я разработал алгоритм, который работает за O (n ^ 2 lgn) времени. Я думаю, что это правильно ... Код написан на C ++ ...

int Search_Closest(A,p,q,n)  /*Returns the index of the element closest to n in array 
                                  A[p..q]*/

{
   if(p<q)
   {
      int r = (p+q)/2;
      if(n==A[r])
         return r;
      if(p==r)
         return r;
      if(n<A[r])
         Search_Closest(A,p,r,n);
      else 
         Search_Closest(A,r,q,n);
   }
   else
      return p;
 }



   int no_of_triangles(A,p,q) /*Returns the no of triangles possible in A[p..q]*/
   {
      int sum = 0;
      Quicksort(A,p,q);  //Sorts the array A[p..q] in O(nlgn) expected case time
      for(int i=p;i<=q;i++)
          for(int j =i+1;j<=q;j++)
           {
               int c = A[i]+A[j];
               int k = Search_Closest(A,j,q,c);
               /* no of triangles formed with A[i] and A[j] as two sides is (k+1)-2 if A[k] is small or equal to c else its (k+1)-3. As index starts from zero we need to add 1 to the value*/
               if(A[k]>c)
                    sum+=k-2;
               else 
                    sum+=k-1;
            }
       return sum;
   }

Надеюсь, это поможет ........

Answer 7

Кажется, нет лучшего алгоритма, чем O (n ^ 3).В худшем случае сам набор результатов имеет O (n ^ 3) элементов.

Например, если задано n равных чисел, алгоритм должен вернуть n * (n-1) * (n-2) результаты.

Answer 8

N0,N1,N2,...Nn-1
sort
X0,X1,X2,...Xn-1 as X0>=X1>=X2>=...>=Xn-1
choice X0(to Xn-3) and choice form rest two item x1...
choice case of (X0,X1,X2)
check(X0<X1+X2)
OK is find and continue
NG is skip choice rest