4.2 Análisis de las estructuras de control (Brassard y Bratley, 2000, p. 111-117)

Introducción

El análisis de las estructuras de control es fundamental para comprender cómo las diferentes construcciones en un programa afectan el flujo de ejecución y la eficiencia de los algoritmos. Estas estructuras incluyen condicionales, bucles y otras formas de control de flujo que definen la secuencia de instrucciones.

Principales estructuras de control

1. Condicionales (if, else)

• Permiten ejecutar bloques de código condicionalmente.
• El análisis se centra en evaluar las condiciones y el costo asociado a la evaluación de estas condiciones y de los bloques ejecutados.

2. Bucles (for, while)

• Ejecutan repetidamente un bloque de código mientras se cumpla una condición.
• El análisis de estos bucles ayuda a estimar su complejidad en función del número de iteraciones, que puede depender del tamaño de entrada.

3. Sentencias de control adicionales

• Incluyen switch, do-while, y saltos (break, continue, goto).
• Su impacto en la eficiencia depende de cómo modulan la ejecución del flujo del programa.

Análisis del impacto en el rendimiento

• La evaluación de estructuras de control considera el número de veces que se ejecutan ciertos bloques.
• La complejidad se expresa comúnmente en notación asintótica, considerando las condiciones y los bucles principales.

Ejemplo de análisis

Supongamos un bucle for que recorre n elementos:

for (i = 0; i < n; i++) {
  // operacion O(1)
}

Principales estructuras de control

1. Condicionales (if, else)

• Permiten ejecutar bloques de código en función de una evaluación lógica.
• El análisis se centra en la evaluación de la condición y en los bloques que se ejecutan.
• Normalmente, la evaluación de condiciones simples es coste O(1), aunque condiciones complejas pueden variar.

2. Bucles (for, while)

• Ejecutan repetidamente un bloque de código mientras la condición sea verdadera.
• La complejidad depende del número de iteraciones, que generalmente está relacionado con el tamaño de entrada n.
• Ejemplo: