Saltar a contenido

Ejercicios · Estructuras C3

Introducción a la complejidad computacional: el cortocircuito de && y ||, por qué el reloj no mide el algoritmo, el conteo de instrucciones con la evaluación que sale del ciclo, el mejor y el peor caso y los ciclos anidados. Cada enlace abre una actividad que se trabaja directo en el navegador, en el mismo orden de los temas de la sesión. Los programas y los arreglos no son los de la sesión: mismo tema, ronda nueva. Las más exigentes son corte y parejas.

Los operadores de cortocircuito

cortocircuito

Cuántas veces se evalúa cada lado de i < n && datos[i] != 0 con y sin un cero, lo que lee & en la última vuelta, tres condiciones unidas con || y el orden de los lados.

El reloj no mide el algoritmo

reloj

Un programa medido con time con tres tamaños, tres corridas iguales que no coinciden, lo que cambia con -O2 y el conteo de instrucciones con m = 70.

El ciclo y la evaluación que sobra

cuadrados

Un ciclo que arranca en 1 y compara con <=: cuántas veces se evalúa la condición, la tabla de conteo línea por línea y T(m).

Cuando el conteo depende de los datos

rango

El mayor menos el menor de un arreglo con dos if adentro del ciclo: cuatro entradas del mismo tamaño, cuál es el mejor caso y T en el mejor y el peor.

El mismo código, dos comportamientos

corte

La búsqueda del último cero que se detiene al encontrarlo: la traza con dos ceros, los dos extremos con n = 5, T en términos de n y cuál caso se reporta.

Un ciclo adentro de otro

parejas

Dos ciclos anidados con tamaños n y m: las evaluaciones del ciclo de adentro, T(n, m) y lo que pasa si m no crece.