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

Ответ 1

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

• 1 1 1
• 1 2 2
• 1 3 3
• 2 2 2
• 2 2 3
• 2 3 3
• 3 3 3

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

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

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

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

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

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 во втором издании). Поиск сложности путем подсчета вложенных циклов иногда является неправильным. Здесь я стараюсь объяснить это как можно проще. Пусть fix я переменная. Тогда для этого я мы должны перебирать j из я в n (это означает, что O (n) операция), а внутренний while цикл итерации k от я до n (это также означает операцию O (n)). Примечание. Я не запускаю цикл с начала для каждого j. Нам также нужно сделать это для каждого я от 0 до n. Поэтому он дает нам n * (O (n) + O (n)) = O (n ^ 2).

Ответ 2

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

Ответ 3

В O(n^2*logn) есть простой алгоритм.

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

И теперь:

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

Это можно просто выполнить путем двоичного поиска этих двух значений (дважды O(logn), это создает два индекса) и подсчета количества элементов между ними.

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

Ответ 4

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

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;
   }

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

Ответ 5

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

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

Ответ 6

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

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

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

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

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

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

Рассмотрим 'arr [i]' как 'a,' arr [j] 'как b и все элементы между' arr [j + 1] 'и' arr [k] 'как' c. Вышеупомянутые условия (ii) и (iii) выполняются, потому что 'arr [i] arr [j] обр [к]. И мы проверяем условие (i), когда мы выбираем 'k'

4.Инкремент 'j снова зафиксирует второй элемент.

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

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

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

Ответ 7

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

Ответ 8

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

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