Complejidad
La complejidad de un algoritmo se refiere a la cantidad de recursos, como el tiempo y la memoria, que requiere para ejecutarse en función del tamaño de la entrada. En otras palabras, la complejidad de un algoritmo describe cómo aumenta la cantidad de trabajo que realiza el algoritmo a medida que aumenta el tamaño del problema que está resolviendo.
Cuando queremos expresar la complejidad en el peor de los casos usamos la Big-O notation
Para el calculo de complejidades debemos saber que una instrucción tiene una complejidad constante mientras que un bucle tiene una complejidad variable dependiente de el tamaño de la variable de entrada
Cuando tenemos una secuencia de bloques (instrucciones, bucles, funciones, etc..), simplificamos la complejidad del bloque inicial a la mayor complejidad entre las de sus bloques anidados
Esto quiere decir que la complejidad de un bloque con una operacion (
O(1)) y un bucle (O(n)), la complejidad total de dicho bloque será (O(n)) por ser la mayor de todos sus bloques anidadosUna operación es eficiente si su complejidad es de
Una lista es válida para ser implementado como una pila ó cola en función de la complejidad de sus operaciones
Es valido para una pilaSi las operacionesconstruir,primero,restoóinsertarFinal,ultimo,borrarFinalson , es cuyo caso la estructura podrá se válida para ser una pila si es eficiente por delante o por detrás o por ambos ladosSi las operacionesconstruir,ultimo,borrarFinalóinsertarFinal,primero,restoson , es cuyo caso la estructura podrá se válida para ser una cola si es eficiente añadiendo por delante y sacando por detrás ó si es eficiente añadiendo por detrás y sacando por delante
LISTA | CREAR VACIA | CONSTRUIR | PRIMERO | RESTO | BORRAR ELEMENTO |
LISTA ENLAZADA SIMPLE | O(1) | O(1) | O(1) | O(1) | O(n) |
LISTA ESTÁTICA SIMPLE | O(1) | O(1) | O(1) | O(1) | O(n) |
DOBLEMENTE ENLAZADA | O(1) | O(1) | O(1) | O(1) | O(n) |
PUNTERO CABECERA FINAL | O(1) | O(1) | O(1) | O(1) | O(n) |
CIRCULAR ESTÁTICA | O(1) | O(1) | O(1) | O(1) | O(n) |
CIRCULAR CON PUNTERO FINAL | O(1) | O(1) | O(1) | O(1) | O(n) |
ESTÁTICA SIMULADA | O(n) | O(1) | O(1) | O(1) | O(n) |
LISTA | PERTENECE | INSERTAR FINAL | ÚLTIMO | BORRAR FINAL |
LISTA ENLAZADA SIMPLE | O(n) | O(n) | O(n) | O(n) |
LISTA ESTÁTICA SIMPLE | O(n) | O(n) | O(1) | O(n) |
DOBLEMENTE ENLAZADA | O(n) | O(n) | O(n) | O(n) |
PUNTERO CABECERA FINAL | O(n) | O(1) | O(1) | O(n) |
CIRCULAR ESTÁTICA | O(n) | O(1) | O(1) | O(1) |
CIRCULAR CON PUNTERO FINAL | O(n) | O(1) | O(1) | O(n) |
ESTÁTICA SIMULADA | O(n) | O(n) | O(n) | O(n) |