Clase 4. Ciclos dependientes y sumatorias¶
Miércoles 19 de agosto de 2026.
La clase 3 quedó abierta en su ejercicio de cierre: un ciclo adentro de otro donde el interno depende del externo. Hoy ese ejercicio deja de ser un reto y se convierte en el punto de partida de un método general, porque la regla ``anidar multiplica'' de la clase pasada tiene una letra menuda que toca leer con cuidado.
Diapositivas¶
El ejercicio pendiente¶
int triangulo(int n) {
int i = 0;
int cuenta = 0;
while (i < n) {
int j = 0;
while (j < i) {
cuenta = cuenta + 1;
j = j + 1;
}
i = i + 1;
}
return cuenta;
}
La entrada es un entero \(n \geq 0\); la salida que interesa es \(T(n)\), el total de instrucciones que la función ejecuta. Antes de contar nada, la prueba de escritorio con \(n = 4\), una fila por cada vuelta del ciclo externo:
| \(i\) | Valores de \(j\) | Vueltas del cuerpo interno | cuenta |
|---|---|---|---|
| 0 | ninguno | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 2 | 0, 1 | 2 | 3 |
| 3 | 0, 1, 2 | 3 | 6 |
triangulo(4) devuelve 6. Y ese valor no es decorativo: como el cuerpo
interno solo hace cuenta = cuenta + 1, la propia función lleva el
registro de cuántas veces corrió su cuerpo.
Multiplicar predice 16; la traza dice 6¶
La clase pasada cerró con la regla de que un ciclo adentro de otro
multiplica. Si se aplica aquí sin mirar más: el externo da \(n\) vueltas, el
interno daría \(n\) vueltas cada vez, el cuerpo correría \(n \cdot n\) veces.
Con \(n = 4\) eso predice que cuenta termina en 16.
Pero la traza entrega 6.
El problema está en la condición j < i. El ciclo interno no hace siempre
lo mismo: con \(i = 0\) da cero vueltas, con \(i = 3\) da tres. La cantidad de
trabajo de cada pasada depende del índice externo.
Multiplicar exige independencia
La regla `anidar multiplica'' vale solo cuando el ciclo interno da la
misma cantidad de vueltas en cada pasada del externo, como ensuma_productos, donde la condición eraj < n`. Si las vueltas del
interno dependen del índice externo, multiplicar cuenta de más.
Ver el patrón¶
Si multiplicar no sirve, la traza sí. La columna de vueltas del ciclo interno crece de uno en uno:
| \(i\) | Vueltas del cuerpo interno |
|---|---|
| 0 | 0 |
| 1 | 1 |
| 2 | 2 |
| 3 | 3 |
Con \(n = 5\) aparece una fila más y nada cambia de forma: \(0 + 1 + 2 + 3 + 4 = 10\). Con \(n = 100\), la suma tiene cien términos y nadie quiere escribirlos. Hacen falta dos cosas: una notación corta para la suma y una fórmula que la resuelva.
El método: congelar y sumar
Para contar un ciclo dependiente: congele el índice externo \(i\), cuente el ciclo interno como una función de \(i\), y sume ese conteo sobre todas las vueltas del externo.
Aplicado de una vez: con \(i\) congelado, la línea cuenta = cuenta + 1;
corre \(i\) veces, así que en total corre \(0 + 1 + 2 + \cdots + (n-1)\)
veces.
La notación para sumas largas¶
Esa suma se abrevia con el símbolo \(\Sigma\):
Abajo van la variable y su valor inicial; arriba, el último valor que toma; a la derecha, el término que se suma en cada paso. El caso pequeño es la traza escrita en una línea:
Una suma \(\sum_{i=a}^{b}\) tiene \(b - a + 1\) términos: los enteros de \(a\) a \(b\), ambos incluidos. Ese ``ambos incluidos'' es la misma aritmética de contar posiciones en un arreglo, y se olvida con la misma facilidad.
Sumar una constante¶
Si el término no depende de la variable de la suma, sumar es multiplicar por el número de términos:
Dos casos que aparecen todo el tiempo al contar ciclos:
El segundo es la trampa clásica: dentro de la suma, \(n\) es una constante, porque no cambia cuando \(i\) avanza. Se suma \(n\) veces el valor \(n\) y el resultado es \(n^2\), no \(n\).
La suma de Gauss¶
¿Cuánto vale \(1 + 2 + \cdots + 100\), sin sumar los cien términos? El truco es escribir la suma de ida y de vuelta, alineadas, y sumar por columnas:
Cada columna suma 101 y hay 100 columnas:
El mismo argumento con \(m\) en lugar de 100 da la fórmula general:
La verificación de rigor con el caso más pequeño: \(1 + 2 + 3 = 6\) y \(\frac{3 \cdot 4}{2} = 6\). En las diapositivas está el dibujo que hace la fórmula evidente: dos escaleras de \(1 + 2 + 3 + 4\) encajan en un rectángulo de \(4 \times 5\), así que \(2S = 4 \cdot 5\).
En los ciclos, \(i\) suele arrancar en 0 y terminar en \(n - 1\). Se sustituye \(m = n - 1\) (el 0 no aporta):
Y la pregunta pendiente queda respondida: \(\texttt{cuenta}(100) = \frac{99 \cdot 100}{2} = 4950\).
Las sumas se separan¶
Dos reglas más, que permiten desarmar una suma nueva en sumas conocidas:
Aplicadas de inmediato a una suma que va a salir en el conteo:
El formulario¶
| Suma | Fórmula cerrada |
|---|---|
| \(\sum_{i=a}^{b} k\) | \(k(b-a+1)\) |
| \(\sum_{i=1}^{m} i\) | \(\frac{m(m+1)}{2}\) |
| \(\sum_{i=0}^{n-1} i\) | \(\frac{(n-1)\,n}{2}\) |
| \(\sum_{i=1}^{m} i^2\) | \(\frac{m(m+1)(2m+1)}{6}\) |
| \(\sum_{i=0}^{n-1} i^2\) | \(\frac{(n-1)\,n\,(2n-1)}{6}\) |
Las dos primeras filas se dedujeron en la sesión; las de los cuadrados quedan de referencia para cuando un conteo las pida, que será pronto. Todas están en CLRS, apéndice A, sección A.1.
El conteo completo¶
Con el formulario listo, triangulo línea a línea. Las líneas del ciclo
interno se escriben como sumatorias sobre \(i\):
| Línea | Veces |
|---|---|
int i = 0; |
1 |
int cuenta = 0; |
1 |
while (i < n) |
\(n + 1\) |
int j = 0; |
\(n\) |
while (j < i) |
\(\sum_{i=0}^{n-1} (i+1)\) |
cuenta = cuenta + 1; |
\(\sum_{i=0}^{n-1} i\) |
j = j + 1; |
\(\sum_{i=0}^{n-1} i\) |
i = i + 1; |
\(n\) |
return cuenta; |
1 |
Con \(i\) congelado el cuerpo interno da \(i\) vueltas y su condición se evalúa \(i + 1\) veces: la evaluación que falla también cuenta, igual que en la clase pasada.
Las sumas ya están cerradas: \(\sum (i+1) = \frac{n(n+1)}{2}\) y \(\sum i = \frac{(n-1)\,n}{2}\), la segunda dos veces. El total:
La prueba del caso pequeño
Antes de creerle a la fórmula, se cuenta a mano un caso chico. Con
\(n = 2\): dos inicializaciones, tres evaluaciones de la condición
externa, dos int j = 0;, tres evaluaciones de la condición interna
(\(1 + 2\)), dos instrucciones del cuerpo interno, dos incrementos de
\(i\) y un return: 15. Y la fórmula:
\(T(2) = \frac{12 + 10}{2} + 4 = 15\). Si no cuadra, alguna suma quedó
mal cerrada; esta comprobación es parte del método, no un adorno.
El triángulo y el cuadrado¶
El costo del triángulo, \(\frac{3n^2+5n}{2} + 4\), contra el del anidado completo de la clase pasada, \(3n^2 + 4n + 4\):
| \(n\) | triangulo |
Anidado completo |
|---|---|---|
| 10 | 179 | 344 |
| 100 | 15 254 | 30 404 |
| 1000 | 1 502 504 | 3 004 004 |
El triángulo hace la mitad del trabajo, y se ve en el dibujo de las vueltas: la fila \(i\) tiene \(i\) celdas encendidas, la mitad de la cuadrícula de \(n \times n\). Pero al multiplicar \(n\) por 10 ambos costos se multiplican por cerca de 100: la dependencia rebaja la constante, no el ritmo de crecimiento. Los dos son cuadráticos.
Otras dependencias¶
El límite se corre en uno¶
El mismo ciclo con j <= i en lugar de j < i:
int contar_incluida(int n) {
int i = 0;
int cuenta = 0;
while (i < n) {
int j = 0;
while (j <= i) {
cuenta = cuenta + 1;
j = j + 1;
}
i = i + 1;
}
return cuenta;
}
Con \(i\) congelado, \(j\) recorre \(0, \ldots, i\): son \(i + 1\) vueltas y el patrón es \(1, 2, 3, 4\). El cuerpo corre
veces, y contar_incluida(4) \(= 10\). El triángulo ahora incluye la
diagonal: cada fila trae una celda más.
El ciclo interno arranca en \(i\)¶
Sumar los productos de todas las parejas \((i, j)\) con \(i \leq j\):
int suma_parejas(int datos[], int n) {
int suma = 0;
int i = 0;
while (i < n) {
int j = i;
while (j < n) {
suma = suma + datos[i] * datos[j];
j = j + 1;
}
i = i + 1;
}
return suma;
}
Con \(i\) congelado, \(j\) recorre \(i, i+1, \ldots, n-1\): son \(n - i\) vueltas. Con \(n = 6\) el patrón baja en lugar de subir: \(6, 5, 4, 3, 2, 1\). La suma se cierra con la linealidad:
El mismo total de contar_incluida: es el mismo triángulo mirado desde
el otro lado.
El conteo completo, con la misma tabla de siempre:
| Línea | Veces |
|---|---|
int suma = 0; |
1 |
int i = 0; |
1 |
while (i < n) |
\(n + 1\) |
int j = i; |
\(n\) |
while (j < n) |
\(\sum_{i=0}^{n-1} (n-i+1) = \frac{n(n+1)}{2} + n\) |
suma = suma + datos[i] * datos[j]; |
\(\frac{n(n+1)}{2}\) |
j = j + 1; |
\(\frac{n(n+1)}{2}\) |
i = i + 1; |
\(n\) |
return suma; |
1 |
La prueba del caso pequeño, con \(n = 1\): dos inicializaciones, dos
evaluaciones externas, un int j = i;, dos evaluaciones internas, dos
instrucciones del cuerpo, un incremento y un return: 11. Y
\(T(1) = \frac{14}{2} + 4 = 11\).
Cuando el índice se duplica¶
Hasta ahora el índice suma. ¿Y si se multiplica?
int potencias(int n) {
int i = 1;
int cuenta = 0;
while (i <= n) {
cuenta = cuenta + 1;
i = i * 2;
}
return cuenta;
}
La traza con \(n = 20\):
| Evaluación | \(i\) | ¿\(i \leq 20\)? | Acción |
|---|---|---|---|
| 1 | 1 | cierto | cuenta \(= 1\), \(i = 2\) |
| 2 | 2 | cierto | cuenta \(= 2\), \(i = 4\) |
| 3 | 4 | cierto | cuenta \(= 3\), \(i = 8\) |
| 4 | 8 | cierto | cuenta \(= 4\), \(i = 16\) |
| 5 | 16 | cierto | cuenta \(= 5\), \(i = 32\) |
| 6 | 32 | falso | sale del ciclo |
Cinco vueltas para \(n = 20\); con \(n = 1000\), \(i\) toma \(1, 2, 4, \ldots, 512\) y para en 1024: diez vueltas.
| \(n\) | Vueltas |
|---|---|
| 10 | 4 |
| 20 | 5 |
| 100 | 7 |
| 1000 | 10 |
| \(10^6\) | 20 |
Las vueltas son la cantidad de veces que 1 se puede duplicar sin pasar de \(n\). Ese número se llama logaritmo en base 2 de \(n\): el exponente al que hay que elevar 2 para llegar a \(n\). Redondeado hacia abajo,
El conteo completo:
| Línea | Veces |
|---|---|
int i = 1; |
1 |
int cuenta = 0; |
1 |
while (i <= n) |
\(\lfloor\log_2 n\rfloor + 2\) |
cuenta = cuenta + 1; |
\(\lfloor\log_2 n\rfloor + 1\) |
i = i * 2; |
\(\lfloor\log_2 n\rfloor + 1\) |
return cuenta; |
1 |
La prueba del caso pequeño: con \(n = 20\), \(\lfloor\log_2 20\rfloor = 4\)
y la fórmula da 19. A mano: 2 inicializaciones, 6 evaluaciones de la
condición, 10 instrucciones del cuerpo y un return: 19. Multiplicar
\(n\) por mil suma unas diez vueltas; es el crecimiento más lento que ha
aparecido en el curso, el logarítmico.
Un índice multiplicativo no arranca en 0
Si i arrancara en 0, duplicar dejaría \(2 \cdot 0 = 0\): el índice
nunca avanzaría y el ciclo no terminaría. Todo ciclo cuyo índice se
multiplica necesita un punto de partida distinto de cero.
Y la variación de práctica: el mismo ciclo con i = i * 3;. Con
\(n = 20\), \(i\) toma \(1, 3, 9\) y para en 27: tres vueltas. En general
\(\lfloor \log_3 n \rfloor + 1\), con \(T(n) = 3\lfloor\log_3 n\rfloor + 7\).
La base del logaritmo es el factor del salto, igual que en los pasos
aditivos el divisor era el tamaño del paso.
Ejercicios¶
Ejercicio 1¶
Complete la tabla línea a línea de contar_incluida y escriba \(T(n)\).
Las vueltas del cuerpo interno ya quedaron contadas; falta armar la
tabla y sumar la columna. Como referencia para verificar: el resultado
coincide con el de suma_parejas, y no es casualidad, porque los dos
triángulos tienen el mismo tamaño.
Ejercicio 2¶
El límite interno es el doble del índice externo. ¿Cuántas veces corre el cuerpo interno? Escriba \(T(n)\).
int doble_i(int n) {
int i = 0;
int cuenta = 0;
while (i < n) {
int j = 0;
while (j < 2 * i) {
cuenta = cuenta + 1;
j = j + 1;
}
i = i + 1;
}
return cuenta;
}
El patrón de las vueltas es \(0, 2, 4, 6, \ldots\) y el 2 sale de la suma por linealidad.
Ejercicio 3¶
El externo salta de dos en dos y el interno depende de él. Suponga \(n\) par. ¿Cuántas veces corre el cuerpo interno?
int salto_dependiente(int n) {
int i = 0;
int cuenta = 0;
while (i < n) {
int j = 0;
while (j < i) {
cuenta = cuenta + 1;
j = j + 1;
}
i = i + 2;
}
return cuenta;
}
Solo los valores pares de \(i\) aportan. Con \(n\) par, \(i\) toma los valores \(0, 2, \ldots, n-2\); escriba la suma de esos aportes y saque el 2 como factor para cerrar con Gauss.
Ejercicio 4¶
Dos ciclos internos en secuencia: uno crece con \(i\) y el otro decrece.
¿Cuántas veces corren, en total, las dos líneas cuenta = cuenta + 1;?
int complemento(int n) {
int i = 0;
int cuenta = 0;
while (i < n) {
int j = 0;
while (j < i) {
cuenta = cuenta + 1;
j = j + 1;
}
j = 0;
while (j < n - i) {
cuenta = cuenta + 1;
j = j + 1;
}
i = i + 1;
}
return cuenta;
}
Cuente cada ciclo interno por separado y sume los dos totales. Los patrones son \(i\) y \(n - i\): los dos triángulos de la sesión, que juntos llenan el cuadrado.
Ejercicio 5¶
El problema al revés. En triangulo, ¿para qué valor de \(n\) el cuerpo
interno corre exactamente 45 veces? ¿Y para cuál corre 4950 veces?
Aquí no se cuenta: se plantea una ecuación con la fórmula cerrada, \(\frac{n(n-1)}{2} = 45\), y se despeja o se prueban valores. Para 4950, la respuesta ya apareció en la sesión.
Ejercicio 6¶
Tres ciclos anidados: el de j no depende de nadie y el de k depende
de i. ¿Cuántas veces corre cuenta = cuenta + 1;?
int mixto(int n) {
int i = 0;
int cuenta = 0;
while (i < n) {
int j = 0;
while (j < n) {
int k = 0;
while (k < i) {
cuenta = cuenta + 1;
k = k + 1;
}
j = j + 1;
}
i = i + 1;
}
return cuenta;
}
Las dos reglas de la sesión trabajan juntas en el mismo conteo. Congele \(i\): el ciclo de \(k\) corre \(i\) veces y el de \(j\) lo repite \(n\) veces completas, así que el cuerpo aporta \(n \cdot i\) por vuelta externa. Cierre \(\sum n \cdot i\) sacando la constante \(n\) de la suma.
Ejercicio de cierre¶
El límite interno es el cuadrado del índice externo. Encuentre \(T(n)\).
int cuadrado_interno(int n) {
int i = 0;
int cuenta = 0;
while (i < n) {
int j = 0;
while (j < i * i) {
cuenta = cuenta + 1;
j = j + 1;
}
i = i + 1;
}
return cuenta;
}
El formulario de la sesión tiene todo lo necesario.
Para la próxima sesión¶
- Resuelva los ejercicios 1 a 3 y el de cierre con la rutina completa: traza pequeña, patrón, sumatoria, fórmula y comprobación.
- La sesión del viernes es una batería completa de ejercicios; tenga el formulario a mano.
- Compile
contar_incluida.cy verifique quecontar_incluida(5)devuelve 15, el valor que predice \(\frac{n(n+1)}{2}\).
Ejercicios interactivos¶
Cuatro ejercicios de esta clase (triangulo, contar_incluida,
suma_parejas y potencias) se pueden trabajar en el navegador, con
predicción, ejecución paso a paso y el conteo de cada línea en vivo:
página de ejercicios interactivos.
Código de la clase¶
Compilación y ejecución:
gcc -Wall -Wextra archivo.c -o archivo && ./archivo
El ejercicio pendiente
Otras dependencias
El índice se duplica
Ejercicios
Referencias¶
- T. H. Cormen, C. E. Leiserson, R. L. Rivest y C. Stein. Introduction to Algorithms. 4.ª ed., MIT Press, 2022. Sección 2.2 y apéndice A, sección A.1 (Summation formulas and properties).
- R. Thareja. Data Structures Using C. Oxford University Press, 2018. Capítulo 2.