La complejidad de un algoritmo es una función f (n) que mide el tiempo y el espacio utilizados por un algoritmo en términos de tamaño de entrada n.
En informática, la complejidad de un algoritmo es una forma de clasificar qué tan eficiente es un algoritmo, en comparación con otros algoritmos. La atención se centra en cómo aumenta el tiempo de ejecución con el conjunto de datos a procesar. La complejidad computacional y la implementación eficiente del algoritmo son importantes en la computación, y esto depende de estructuras de datos adecuadas.
¿Qué efectos tiene el tiempo de ejecución de un algoritmo?
- Cómo mejorar mi solución Java para el problema 'nodo de hoja izquierda más profundo en un árbol binario'
- ¿Cuál es la mejor fuente en línea para el aprendizaje de algoritmos?
- ¿Qué es la programación dinámica?
- ¿Qué estructura de datos es mejor para implementar una guía telefónica: Trie o Hash? ¿Por qué?
- Cómo implementar una cola de doble finalización sin una lista vinculada
(a) computadora utilizada, la plataforma de hardware
(b) representación de tipos de datos abstractos (ADT)
(c) eficiencia del compilador
(d) competencia del implementador (habilidades de programación)
(e) complejidad del algoritmo subyacente
(f) tamaño de la entrada
Mostraremos que de los anteriores (e) y (f) son generalmente los más significativos.
Tiempo para que un algoritmo ejecute t (n)
Una función de entrada. Sin embargo, intentaremos caracterizar esto por el tamaño de la entrada. Intentaremos estimar el PEOR CASO, y a veces el MEJOR CASO, y muy raramente el CASO PROMEDIO.
¿Qué medimos?
Al analizar un algoritmo, en lugar de un fragmento de código, intentaremos predecir el número de veces que se realiza “la actividad principal” de ese algoritmo. Por ejemplo, si estamos analizando un algoritmo de clasificación, podríamos contar la cantidad de comparaciones realizadas, y si es un algoritmo para encontrar una solución óptima, la cantidad de veces que evalúa una solución. Si se trata de un algoritmo de coloración de gráficos, podríamos contar la cantidad de veces que verificamos que un nodo coloreado sea compatible con sus vecinos.
Peor de los casos
… es el tiempo de ejecución máximo, sobre todas las entradas de tamaño n, ignorando los efectos (a) a (d) anteriores. Es decir, solo consideramos el “número de veces que se realiza la actividad principal de ese algoritmo”.
Mejor caso
En este caso nos fijamos en instancias específicas de entrada de tamaño n. Por ejemplo, podríamos obtener el mejor comportamiento de un algoritmo de ordenación si la entrada ya está ordenada.
Caso promedio
Podría decirse que el caso promedio es la medida más útil. Es posible que el peor de los casos sea patológico y extremadamente raro, y que nos preocupe más cómo funciona el algoritmo en el caso general.
Lamentablemente, esto suele ser algo muy difícil de medir . En primer lugar, debemos ser capaces de definir de alguna manera por lo que queremos decir como la “entrada promedio de tamaño n”. Necesitaríamos saber mucho sobre la distribución de casos en todos los conjuntos de datos de tamaño n. Alternativamente, podríamos hacer una suposición posiblemente peligrosa de que todos los conjuntos de datos de tamaño n son igualmente probables.
Fuente: Introducción al algoritmo por Thomas H. Cormen
