Definición de Algoritmo

Un algoritmo es un conjunto ordenado y finito de instrucciones o pasos que se siguen para resolver un problema o realizar una tarea específica.

Complejidad Algorítmica (Notación Big O)

La complejidad de un algoritmo describe cómo sus requerimientos de tiempo o espacio crecen con el tamaño de la entrada. Se expresa comúnmente usando la notación Big O:

• O(1) – Constante: El tiempo de ejecución no depende del tamaño de la entrada.

• O(log n) – Logarítmica: El tiempo de ejecución crece logarítmicamente con el tamaño de la entrada.

• O(n) – Lineal: El tiempo de ejecución crece linealmente con el tamaño de la entrada.

• O(n log n) – Logarítmico-lineal (o linearítmica): Común en algoritmos de ordenación eficientes.

• O(n²) – Cuadrática: El tiempo de ejecución crece cuadráticamente (común en bucles anidados).

• O(n³) – Cúbica: El tiempo de ejecución crece cúbicamente (y en general O(n^k) para cualquier k entero positivo).

• O(2ⁿ) – Exponencial: El tiempo de ejecución se duplica con cada adición a la entrada (muy ineficiente para entradas grandes).

• O(n!) – Factorial: El tiempo de ejecución crece factorialmente (extremadamente ineficiente).

Algoritmos Iterativos

Los algoritmos iterativos resuelven problemas mediante la repetición de un bloque de instrucciones.

• ¿Qué es un algoritmo iterativo y cómo se diferencia de uno recursivo?

  Un algoritmo iterativo utiliza bucles (como for, while, do-while) para repetir un conjunto de instrucciones un número determinado o indeterminado de veces. A diferencia de un algoritmo recursivo, no se basa en llamadas a sí mismo, sino en la repetición controlada por una condición de parada.

• ¿Cuáles son las estructuras de control más comunes utilizadas en algoritmos iterativos?

  Las estructuras de control de flujo más comunes son los bucles: for (generalmente para un número conocido de iteraciones), while (cuando la condición se verifica antes de cada iteración) y do-while (cuando la condición se verifica después de al menos una iteración).

• ¿Qué significa la eficiencia de un algoritmo iterativo en términos de complejidad temporal y espacial?

  La eficiencia temporal mide el número de operaciones elementales que realiza el algoritmo en función del tamaño de la entrada (tiempo de ejecución). La eficiencia espacial mide la cantidad de memoria adicional que utiliza el algoritmo. Ambas se suelen expresar usando la notación Big O (por ejemplo, O(n), O(log n)).

• ¿Qué es un bucle anidado y cómo afecta su complejidad computacional?

  Un bucle anidado es un bucle que se encuentra dentro del cuerpo de otro bucle. La presencia de bucles anidados generalmente multiplica las complejidades. Por ejemplo, dos bucles anidados donde cada uno itera n veces suelen resultar en una complejidad temporal de O(n²).

• ¿Cómo se implementa la iteración en un lenguaje de programación como C++?

  En C++, la iteración se implementa principalmente mediante las estructuras de bucle for, while y do-while. Se utilizan variables (contadores o indicadores) y condiciones lógicas para controlar el flujo y la terminación del bucle.

• ¿Qué diferencia existe entre un bucle for y un bucle while en cuanto a su estructura y uso?

  • for: Ideal cuando el número de iteraciones es conocido de antemano o se puede determinar fácilmente. Su sintaxis compacta incluye inicialización, condición y expresión de actualización.
  • while: Adecuado cuando el número de iteraciones depende de una condición que puede cambiar durante la ejecución y se debe evaluar antes de cada posible iteración.

• ¿Qué problemas se pueden presentar con bucles infinitos?

  Un bucle infinito ocurre cuando su condición de terminación nunca se cumple. Esto provoca que el programa consuma recursos de CPU y/o memoria de forma indefinida, pudiendo bloquear la aplicación o el sistema y requiriendo una interrupción externa para detenerlo.

• ¿Cuál es la importancia de establecer una condición de parada clara en un algoritmo iterativo?

  Es fundamental. La condición de parada asegura que el bucle terminará eventualmente, evitando bucles infinitos y garantizando que el algoritmo produzca un resultado en un tiempo finito.

• ¿Cómo se puede optimizar un algoritmo iterativo para mejorar su eficiencia?

  La optimización puede incluir: reducir el número total de iteraciones, minimizar el trabajo realizado dentro del bucle, sacar cálculos invariantes fuera del bucle, o elegir estructuras de datos más adecuadas que permitan operaciones más rápidas.

• ¿Cuál es el papel de la inicialización en un algoritmo iterativo?

  La inicialización establece los valores de partida para las variables que se utilizan en el control del bucle (contadores, acumuladores, indicadores de estado). Una inicialización correcta es crucial para el funcionamiento esperado del algoritmo.

Algoritmos Recursivos

Los algoritmos recursivos resuelven problemas dividiéndolos en subproblemas más pequeños del mismo tipo.

• ¿Qué es un algoritmo recursivo y cómo se define formalmente?

  Un algoritmo recursivo es aquel que se invoca a sí mismo para resolver una versión más pequeña del problema original. Formalmente, se define mediante uno o más casos base (condiciones de parada) y un paso recursivo que reduce el problema y llama a la función nuevamente.

• ¿Cuál es la diferencia entre recursión directa e indirecta?

  • Recursión directa: Ocurre cuando una función se llama a sí misma dentro de su propio código.
  • Recursión indirecta: Ocurre cuando una función A llama a una función B, y la función B (o una cadena de llamadas iniciada por B) eventualmente vuelve a llamar a la función A.

• ¿Qué papel juega el caso base en un algoritmo recursivo?

  El caso base es una condición que detiene la secuencia de llamadas recursivas. Define la solución para la versión más simple del problema. Sin un caso base alcanzable, la recursión continuaría indefinidamente, llevando a un error de desbordamiento de la pila (stack overflow).

• ¿Qué es la pila de llamadas (call stack) y cómo afecta a la eficiencia de un algoritmo recursivo?

  La pila de llamadas es una estructura de datos interna que el sistema utiliza para gestionar las llamadas a funciones activas. Cada llamada recursiva añade un nuevo marco (stack frame) a la pila para almacenar su estado local. Una recursión muy profunda puede consumir una cantidad significativa de memoria en la pila, afectando la eficiencia espacial y potencialmente causando un desbordamiento de pila.

• ¿Qué es la recursión de cola (tail recursion) y por qué puede ser más eficiente?

  La recursión de cola ocurre cuando la llamada recursiva es la última operación realizada en la función. Algunos compiladores pueden optimizarla (Tail Call Optimization – TCO) transformándola internamente en una iteración, lo que evita el crecimiento de la pila de llamadas y la hace tan eficiente en espacio como un bucle iterativo.

• ¿Cómo se puede convertir un algoritmo recursivo en un algoritmo iterativo?

  Generalmente, se puede convertir utilizando bucles (while o for). A veces, se requiere el uso explícito de una estructura de datos, como una pila (stack), para simular el comportamiento de la pila de llamadas y mantener el estado entre iteraciones.

• ¿Cuáles son las ventajas y desventajas de utilizar algoritmos recursivos?

  • Ventajas: Suelen ofrecer soluciones más elegantes, concisas y fáciles de entender para problemas que tienen una estructura inherentemente recursiva (como operaciones en árboles, fractales, o ciertas definiciones matemáticas).
  • Desventajas: Pueden ser menos eficientes en términos de tiempo (debido a la sobrecarga de las llamadas a función) y espacio (uso de la pila de llamadas). Existe el riesgo de desbordamiento de pila si la recursión es muy profunda y no hay optimización de cola.

• ¿Qué es un árbol de recursión y cómo se utiliza para analizar un algoritmo recursivo?

  Un árbol de recursión es una representación visual de las llamadas recursivas generadas por un algoritmo para una entrada dada. Cada nodo representa una llamada a la función. Ayuda a visualizar el flujo de ejecución, contar el número total de operaciones y analizar la complejidad temporal del algoritmo (por ejemplo, sumando el trabajo realizado en cada nivel del árbol).

• ¿Cómo afecta la profundidad de recursión a la memoria utilizada por un algoritmo?

  La memoria utilizada (específicamente en la pila de llamadas) es generalmente proporcional a la máxima profundidad de la recursión alcanzada. A mayor profundidad, mayor consumo de memoria en la pila, lo que incrementa el riesgo de desbordamiento.

• ¿Qué es la recursión múltiple y en qué tipo de problemas se utiliza?

  La recursión múltiple ocurre cuando una función realiza más de una llamada recursiva a sí misma en su cuerpo. Es común en algoritmos que exploran múltiples posibilidades o ramas, como en el cálculo de los números de Fibonacci (en su forma recursiva simple), algoritmos de tipo «divide y vencerás» como MergeSort, o al recorrer estructuras de datos como árboles binarios.