Unidad I: Complejidad de Algoritmos

El tiempo que un algoritmo necesita para resolver un problema. Se mide en función del tamaño de la entrada.

La cantidad de memoria que un algoritmo necesita para funcionar. Se mide en función del tamaño de la entrada.

Una medida del tamaño de la entrada de un algoritmo. Por ejemplo, la longitud de un vector, el número de elementos en una matriz o el número de nodos en un grafo.

Una estimación teórica del tiempo de ejecución de un algoritmo, expresada como una función del tamaño de la entrada.

Una medida real del tiempo de ejecución de un algoritmo, obtenida al ejecutar el algoritmo con datos de entrada específicos en un ordenador concreto.

Una función que acota (por arriba o por abajo) el tiempo de ejecución de un algoritmo. Ayuda a entender el comportamiento del algoritmo para diferentes tamaños de entrada.

Conjunto de algoritmos que resuelven el mismo problema.

Determinar cuál de varios algoritmos es el most adecuado para resolver un problema, tomando en cuenta su eficiencia temporal y espacial.

La complejidad de un algoritmo es una medida teórica que compara la eficiencia de diferentes algoritmos. Evalúa el uso de recursos como tiempo y espacio, determinando cómo se desempeñan los algoritmos al resolver un problema.

Las diferentes formas de resolver un problema se traducen en distintos algoritmos. Cada algoritmo puede llevar a una solución única, con diferentes tiempos de ejecución y consumo de memoria.

La complejidad algorítmica ayuda a comprender cómo se comportará un algoritmo cuando se le presenta un gran conjunto de datos. Es esencial para predecir el rendimiento de un algoritmo.

El tiempo que un algoritmo tarda en ejecutarse es crucial para evaluar su eficiencia. Mide cuánto tiempo se necesita para completar el proceso

Espacio de memoria es la cantidad de almacenamiento que se utiliza durante la ejecución de un algoritmo. Se mide en términos de la cantidad de memoria que requiere un algoritmo.

El espacio y el tiempo son dos parámetros cruciales que miden la eficiencia de un algoritmo. Un buen algoritmo utiliza menos memoria y completa la tarea más rápido.

La complejidad algorítmica es un concepto fundamental que se utiliza para comparar y evaluar la eficiencia de algoritmos. Es esencial para tomar decisiones informadas sobre el uso de algoritmos.

El estudio de la complejidad algorítmica requiere de destrezas matemáticas y la aplicación de técnicas específicas. Sin embargo, la comprensión del concepto es relativamente sencilla.

El tamaño de entrada es el número de componentes sobre los que se ejecuta un algoritmo.

Las sentencias sencillas en un algoritmo se ejecutan en un tiempo constante, independientemente del tamaño de entrada.

Una secuencia de sentencias en un algoritmo se ejecuta en un tiempo proporcional a la suma del tiempo de cada sentencia.

Una decisión en un algoritmo, como un 'if', se ejecuta en tiempo constante, más el tiempo de la rama del 'if' que se ejecute.

Los bucles en un algoritmo se ejecutan en un tiempo proporcional al número de iteraciones, multiplicado por el tiempo de ejecución del cuerpo del bucle.

Las instrucciones que no trabajan con estructuras de datos cuyo tamaño depende del problema son consideradas como operaciones de tiempo constante.

La complejidad total de un programa es como sumar las complejidades de cada instrucción.

Se suma la complejidad de la condición más la complejidad de la rama con mayor complejidad, ya sea la rama THEN o la rama ELSE. Para decisiones multiples, como ELSE IF o SWITCH CASE, se toma la complejidad de la rama más compleja.

Si el bucle se ejecuta un número fijo de veces, independiente del tamaño del problema, la complejidad es O(1). Si el bucle se ejecuta un número de veces relacionadas con el tamaño del problema, la complejidad es O(n), donde n es el tamaño del problema.

Si dentro de un bucle se encuentran otros bucles que se ejecutan un número de veces ligado al tamaño del problema, la complejidad se multiplica por cada bucle anidado.

La complejidad de un bucle que se ejecuta un número de veces relacionado con el tamaño del problema, pero en el que la variable de control no se incrementa o decrece de forma lineal, se determina por k = techo(log2(N)), siendo N el tamaño del problema y k el número de iteraciones, lo que da como resultado un complejidad O(log n).

El número de iteraciones necesarias para que un bucle se complete, cuando la variable de control decrece en cada iteración, se calcula como log2(N), con N siendo el tamaño del problema.

La complejidad de las llamadas a procedimientos depende de la complejidad del procedimiento llamado y la frecuencia con que se llama.

Los problemas decidibles son aquellos para los que existe un algoritmo que puede determinar la respuesta, es decir, que se puede resolver en un tiempo finito. Por ejemplo, encontrar la raíz cuadrada de un número dado, es un problema decidible ya que podemos encontrar la raíz cuadrada usando un algoritmo, podemos encontrar la raíz cuadrada usando un algoritmo.

Son problemas decidibles que requieren tantas operaciones que su solución no es factible en la práctica, por lo que se consideran "intratables". Por ejemplo, encontrar el orden de un conjunto de posibles movimientos para resolver un complejo problema en ajedrez en un tiempo limitado.

Son problemas decidibles que se pueden resolver en un tiempo razonable, es decir, con un algoritmo que tiene una complejidad polinomial. Por ejemplo, ordenar una lista de números. Se puede llevar a cabo con un algoritmo que se ejecuta más rápido a medida que aumenta el número de elementos.

La diferencia entre problemas tratables e intratables reside en la complejidad temporal de sus algoritmos. Los problemas tratables tienen algoritmos de complejidad polinomial, mientras que los problemas intratables tienen algoritmos de complejidad exponencial.

Un algoritmo determinístico es un algoritmo que, para la misma entrada, siempre producirá la misma salida. Es predecible y sigue las mismas reglas en cada ejecución.

Son problemas inresolubles mediante ningún algoritmo, por lo que no existen soluciones para ellos. Algunos ejemplos son el problema de la parada (determinar si un programa se detendrá o no) o el problema del halting.

En computación, un algoritmo se considera que se resuelve en tiempo polinomial si su tiempo de ejecución se limita a un valor calculado mediante una fórmula polinomial. Estas fórmulas pueden ser logarítmicas, lineales, cuadráticas o cúbicas.

Los problemas matemáticos se clasifican en dos categorías: indecidibles y decidibles. Los problemas indecidibles no pueden resolverse con algoritmos, mientras que los problemas decidibles sí tienen al menos un algoritmo para su solución.

La teoría de la complejidad computacional busca comprender la eficiencia de los algoritmos. El problema P vs. NP pregunta si todos los problemas que se pueden verificar en tiempo polinomial también se pueden resolver en tiempo polinomial.

Un ejemplo sencillo para entender la complejidad computacional es la raíz cuadrada y el cuadrado de un número. Calcular la raíz cuadrada es más complejo que elevar un número al cuadrado. Comprobar la solución elevando al cuadrado es más eficiente que calcular la raíz cuadrada.

Comprobar una solución puede ser más eficiente que calcularla. La complejidad computacional se evalúa en base a las operaciones necesarias y la eficiencia del método utilizado.