Si n números se dan, ¿cómo puedo encontrar el número total de posibles triángulos? ¿Hay algún método que hace esto en menos de O(n^3) tiempo?

Estoy considerando a+b>c, b+c>a y a+c>b condiciones para ser un triángulo.

  • Sugerencia: ordenar los números, y para cada par (a,b) (b≥a) encontrar todos los cs que satisfacen b≤c≤a+b.
  • pero en el peor de los casos, incluso en avg caso vamos a obtener O(n^3) la complejidad ? O puede ser que estoy mal entendida. U puede elaborar ?
InformationsquelleAutor peeyush | 2011-11-13

8 Comentarios

  1. 51

    Asumir que no hay números iguales en n dado y permitido el uso de un número más de una vez. Por ejemplo, nos dan los números {1,2,3}, por lo que podemos crear 7 triángulos:

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

    Si cualquiera de estos supuestos, no es cierto, es fácil modificar el algoritmo.

    Aquí les presento algoritmo que toma O(n^2) tiempo en el peor caso:

    1. Ordenar números (orden ascendente).
      Vamos a tomar triples ai <= aj <= ak, tales que i <= j <= k.
    2. Para cada i, j que usted necesita para encontrar más grande de k que satisfacen ak <= ai + aj. A continuación, todos los triples (ai,aj,al,) j <= l <= k es el triángulo (porque ak >= aj >= ai sólo podemos violar ak < i+ aj).

    Considerar dos pares (i, j1) y (i, j2) j1 <= j2. Es fácil ver que k2 (que se encuentra en el paso 2 para (i, j2)) >= k1 (que se encuentra a un paso 2 para (i, j1)). Esto significa que si usted iterar j, y sólo se necesita comprobar números a partir del anterior k. Por lo que le da O(n) tiempo de complejidad para cada i, lo que implica O(n^2) para todo el algoritmo.

    Código fuente de 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;
    }

    Actualización para downvoters:

    Esto sin duda es O(n^2)! Por favor, lea cuidadosamente «Una Introducción a los Algoritmos» por Thomas H. Cormen capítulo sobre Análisis Amortizado (17.2 en la segunda edición).
    Encontrar la complejidad contando bucles anidados es completamente equivocado a veces.
    Aquí trato de explicar es tan simple como pudiera. Vamos a arreglar me variable. Entonces para que me debemos recorrer j de me a n (que significa operación O(n)) y la interna bucle while itera k de me a n (también significa operación O(n)). Nota: yo no iniciar el bucle while desde el principio para cada j. También tenemos que hacerlo para cada i desde 0 a n. Esto nos da n * (S(n) + O(n)) = O(n^2).

    • por lo que su bucle while se ejecuta de forma gratuita ? has contado la complejidad de bucle while, ya que sólo el 2 por voluntad de dar O(n^2)
    • Chicos, por favor, lea mi actualización y un aspecto más cuidado. Es O(n^2).
    • Lo que han hecho es simplemente deshonesto y no muy inteligente.
    • mis disculpas .. he corregido mi error también upvoted y aceptado como respuesta 🙂
    • no podemos utilizar una búsqueda binaria para encontrar el valor de «k»? esto reduciría el tiempo de complejidad a nlogn?
    • Su solución es una obra de arte. Abajo los votantes tratar de entender la forma en k se mueve. No se reinicializa en el bucle while cada vez que el algoritmo logra O(n^2) complejidad
    • No binario de búsqueda no le dará una complejidad de O(nlogn).Por qué? Debido a su outerloop (i) se ejecuta n veces. El bucle para k se ejecuta n veces y su lazo con la j también se ejecuta n veces. Si usted cambia de k para una búsqueda binaria , se llevará a cabo logn tiempo, pero su complejidad todavía será O(n^2) debido a que los lazos dentro de la voluntad tiene una complejidad de O(n)+O(logn) = O(n). Yeah ! Va a ser más eficiente a pesar de que
    • gran respuesta y el inteligente análisis de tiempo de ejecución

  2. 4

    Si utiliza un orden binario, que es O(n log(n)), derecho? Mantenga su árbol binario a mano, y para cada par (a,b) donde b y c < (a+b).

    • así que puedo esperar de O(n^2 logn) la complejidad de aquí, ¿verdad ?
    • siempre evalúe a false, ver mi respuesta
    • si usted se refiere en su párrafo acerca de las desigualdades y de la simetría, que tiene algunas fallas graves. Es algún tipo de broma?
    • en realidad no, no es una broma 🙂 sí, eso fue un poco precipitado.
    • Lo siento, pero esta no es una respuesta y O(n-log(n)) cosas es incorrecta.
    • Entendí que por error fue n-largo(n) y debe ser O(n logn), ya que no cochecito algoritmo puede ordenar en menos de esto. Por otra parte esto me dio la idea para reducir la complejidad de O(n^3) a O(n^2 logn). Así que me marca este correcto. Quien niega que la respuesta debe deshacer esto.
    • lo siento, no implica en todo algoritmo es O(n logn), justo el tipo de pieza.

  3. 4

    Hay un algoritmo sencillo O(n^2*logn).

    • Suponga que usted desea que todos los triángulos como triples (a, b, c) donde a <= b <= c.
    • Hay 3 triángulo de las desigualdades, pero sólo a + b > c basta (a los demás, a continuación, mantenga trivialmente).

    Y ahora:

    • Ordenar la secuencia en la O(n * logn), por ejemplo, por merge-sort.
    • Para cada par (a, b), a <= b el valor restante c debe ser de al menos b y menos de a + b.
    • Por lo que necesita para contar el número de elementos en el intervalo de [b, a+b).

    Esto puede ser simplemente hecho por binario de búsqueda a+b (O(logn)) y contar el número de elementos en [b,a+b) para cada posibilidad que es b-a.

    Todos juntos O(n * logn + n^2 * logn) que es O(n^2 * logn). Espero que esto ayude.

    • david ya dio el mismo enfoque antes de esto.
    • Sí, pero la complejidad es justo aquí. BTW, @cartesius00, usted sabe que el índice de b, no hay necesidad de binarios de búsqueda de la misma.
  4. 2

    Deje a, b y c tres lados. La siguiente condición debe mantener durante un triángulo (la Suma de dos lados es mayor que el tercer lado)

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

    Siguientes son los pasos para contar triángulo.

    1. Ordenar la matriz en la no-orden decreciente.

    2. Inicializar dos punteros ‘i’ y ‘j’ para el primer y segundo elementos, respectivamente, y inicializar el conteo de triángulos como 0.

    3. Arreglar ‘i’ y ‘j’ y encontrar a la derecha del índice » k » (o el más grande ‘arr[k]’) tal que ‘arr[i] + arr[j] > arr[k]’. El número de triángulos que se pueden formar con ‘arr[i]’ y ‘arr[j]’ dos caras ‘k – j’. Agregar ‘k – j’ a contar de triángulos.

    Consideremos ‘arr[i]’ como ‘a’, ‘arr[j] como b y de todos los elementos entre ‘arr[j+1]’ y ‘arr[k]’ como ‘c’. Las condiciones anteriormente mencionadas (ii) y (iii) están satisfechos porque ‘arr[i] < arr[j] < arr[k]’. Y verificamos la condición (i) cuando captamos ‘k’

    4.Incremento de la ‘j’ para fijar el segundo elemento nuevo.

    Tenga en cuenta que en el paso 3, se puede utilizar el anterior valor de ‘k’. La razón es simple, si sabemos que el valor de ‘arr[i] + arr[j-1]’ es mayor que ‘arr[k]’, entonces podemos decir ‘arr[i] + arr[j]’ también será mayor que ‘arr[k]’, porque la matriz está ordenada en orden creciente.

    5.Si ‘j’ ha llegado al final, luego de incremento ‘yo’. Inicializar ‘j’ como ‘i + 1’, ‘k’ como ‘+2’) y repita los pasos 3 y 4.

    Tiempo de Complejidad: O(n^2).
    El momento en que la complejidad se ve más porque de los 3 bucles anidados. Si echamos un vistazo más de cerca en el algoritmo, se observa que el valor de k se inicializa sólo una vez en la parte más externa de bucle. La más interna de bucle se ejecuta en la mayoría de O(n) tiempo de cada iteración del bucle más externo, debido a k se inicia desde la i+2 y va hasta n para todos los valores de j. Por lo tanto, el tiempo, la complejidad es O(n^2).

  5. 1

    He trabajado un algoritmo que se ejecuta en O(n^2 lgn) tiempo. Creo que es correcto…
    El código es wtitten en 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;
       }

    Espero que ayude……..

    • es lo mismo como david respondió.
    • Yo tenía una solución similar, excepto que yo estaba buscando la más cercana par de lados, no es el más cercano de un solo lado. El problema de estas soluciones es que ellos producen o los recuentos de los mismos triángulos varias veces (por ejemplo, trillizos 3<4+5, 4<3+5 y 5<3+4 describen el mismo triángulo, pero están todos contados). Una vez que se intenta eliminar duplicados de triángulos, inmediatamente golpear O(nnn) la complejidad.
    • es por eso que nos quite duplicacy antes de comprobar la condición. Como una vez que hemos 3,4,5; no podemos volver a 4,5,3. Como i=0; i<n;i++ entonces j=i+1;j<n;j++
    • Me encontré con el código anterior como-es y la mía con duplicados suprimida. El código de arriba claramente producido más soluciones que realmente existían.
  6. 1

    posible respuesta

    Aunque podemos utilizar una búsqueda binaria para encontrar el valor de » k » por lo tanto mejorar el tiempo de complejidad!

    • Esto no proporciona una respuesta a la pregunta. Para la crítica o la solicitud de aclaración de un autor, deja un comentario debajo de su post.
    • es el vínculo para contar el número de triángulos a partir de una matriz!
    • ellos también han dado a este TAN enlace como referencia … uno más bucle de ahora 😉
  7. -1
    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
    • ¿qué acerca de la complejidad ? función de elección elige X0 , X1 y X2, debido a esto, sigue siendo O(n^3), aunque en algunos casos debido a saltarse nos puede ahorrar tiempo, pero no siempre.
    • Si todo está OK combinación(en el peor caso?), todas las combinaciones deben ser examinadas (unskipable) como usted podría pensar, pero (X0, X1, X2) como si el omitir cuando NG, (X0, Xn-2, Xn -1) es ACEPTAR cuando el proceso de verificación capaz de saltar. así que usted puede algo omitir cualquier caso.
    • así que usted piensa que saltarse algunos casos reducir la complejidad ?
    • Bueno, yo creo que el efecto se pierde y el procedimiento es muy complejo.
  8. -1

    Parece que no hay mejor algoritmo de O(n^3). En el peor de los casos, el conjunto de resultados en sí tiene O(n^3) elementos.

    Por Ejemplo, si n la igualdad de los números, el algoritmo tiene que devolver n*(n-1)*(n-2) resultados.

    • divertido, podría haber sido mucho más divertido, c>d y c>a-b no implica que d>a-b :-).
    • omg, eso es un poco embarazoso 🙂
    • ahora, eso es un resultado válido (eso espero) 🙂
    • He quitado la antigua parte de mi respuesta para no causar confusión.
    • n^logn es mucho más que alguna polinomio
    • Editado : creo que David la explicación que da (n^2 logn) algoritmo, ya que incluso en el caso de n igual no va a trabajar, y la búsqueda de c se puede hacer en logn tiempo para cada a y b.

Dejar respuesta

Please enter your comment!
Please enter your name here