Complejidad temporal de un bucle anidado triple

Respuestas:

14

Puede contar la cantidad de veces que se ejecuta el bucle for más interno contando la cantidad de tripletes para los que se ejecuta.(i,j,k)

Por las condiciones del bucle sabemos que: 1ijkn . Podemos reducirlo al siguiente problema de combinatoria simple.

  • Imagina n+2 cajas de color rojo colocadas en una matriz de izquierda a derecha.
  • Elige 3 cajas de cajas y píntalas de azul.n+2
  • Forme un triplete (i,j,k) siguiente manera:
    • i = 1 + número de cuadros de color rojo a la izquierda del primer cuadro azul.
    • j = 1 + número de cuadros de color rojo a la izquierda del segundo cuadro azul.
    • = 1 + número de cuadros de color rojo a la izquierda del tercer cuadro azul.k

Entonces, solo necesitamos contar el número de formas de elegir 3 cajas de cajas que es ( n + 2n+2 .(n+23)

rizwanhudda
fuente
2
¡Buena respuesta! Los valores exactos de i, j, k no son importantes. Solo necesitamos saber que cualquier caja azul se puede colocar en n posiciones posibles y que sus posiciones están delimitadas: el segundo siempre viene después del primero y antes del tercero.
Dávid Natingga
@rizwanhudda Claro excepto por el parte en n + 2 . ¿Puedes explicarlo por favor? n + 3 se parece al número correcto. +2n+2n+3
saadtaame
1
@saadtaame Sí. Puede imaginar tener cuadros rojos, pero tener libertad para elegir 3 cuadros rojos para pintar de azul entre " n + 2 cuadros rojos", ya que no puede colorear el primer cuadro como azul (ya que i 1 )n+3n+2i1
rizwanhudda
3

para mí, es más fácil notar que el bucle interno se ejecuta veces y el número total de ejecuciones en el bucle interno esni

(ni)+(ni1)+(ni2)++1

esto se puede reescribir como y se ejecuta n veces, por lo que el número total de ejecuciones esj=0ninijn

yo=0 0nortej=0 0norte-yonorte-yo-j=norte(norte+1)(norte+2)6 6
andy mcevoy
fuente
Un desafío para ti: imagina que tienes un ciclo x-anidado. Según la respuesta anterior, se ejecutaría (n + x-1) elegir x veces. ¿Cómo calcularías tu fórmula?
Dávid Natingga
¡afortunadamente el OP no pidió x-nested! ¿Cómo se expande la otra respuesta dada a un ciclo anidado x? Mi respuesta debería obtener más sumas yendo de 0 a n, 0 a n-i_1, 0 a n-i_2, ..., 0 a n-i_x. Pero no sabría cómo calcular eso.
Andy mcevoy
1
La respuesta no se expande explícitamente para una x general, pero el proceso de razonamiento presentado es fácil de seguir para los bucles anidados en x. Simplemente agrega más cuadros azules. Tampoco sé cómo calcularía esas sumas más.
Dávid Natingga