Complejidad temporal de un bucle anidado triple

13

Considere el siguiente bucle triple anidado:

for (int i = 1; i <= n; ++i)
    for (int j = i; j <= n; ++j)
        for (int k = j; k <= n; ++k)
            // statement

La declaración aquí se ejecuta exactamente veces ¿Podría alguien explicar cómo se obtuvo esta fórmula? Gracias. $n(n+1)(n+2)\over6$

algorithms time-complexity algorithm-analysis Xin
fuente

1

La pregunta La fórmula de la complejidad del tiempo de los bucles anidados también podría ser de interés.

Juho

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: $1 \leq i \leq j \leq k \leq n$ . 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 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+2$ . $n+2 \choose 3$

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

. ¿Puedes explicarlo por favor?

parece al número correcto.

+ 2

$+2$

n + 2

$n+2$

n + 3

$n+3$

saadtaame

1

@saadtaame Sí. Puede imaginar tener

cuadros rojos, pero tener libertad para elegir 3 cuadros rojos para pintar de azul entre "

cuadros rojos", ya que no puede colorear el primer cuadro como azul (ya que

)

n + 3

$n+3$

n + 2

$n+2$

i \geq 1

$i \geq 1$

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 es $n-i$

$(n-i)+(n-i-1)+(n-i-2)+\ldots+1$

esto se puede reescribir como y se ejecuta veces, por lo que el número total de ejecuciones es $\sum_{j=0}^{n-i} n-i-j$ $n$

\sum_{yo = 0 0}^{norte} \sum_{j = 0 0}^{norte - yo} norte - yo - j = \frac{norte (norte + 1) (norte + 2)}{6 6}

$\sum_{i=0}^{n}\sum_{j=0}^{n-i} n-i-j=\frac{n(n+1)(n+2)}{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

Complejidad temporal de un bucle anidado triple

Respuestas: