Complejidad Algoritmica
Introducción
Complejidad espacial: idea de la memoria que necesita el algoritmo para resolver un problema.
Complejidad temporal: idea del tiempo que consume un algoritmo para resolver un problema.
Cuánto tarda en resolver un problema.
No hablamos de seg ni mseg, sino de unidades de tiempo.
La complejidad se calcula en funcion de un tamano generico del problema.
Lo que realmente queremos saber es como crece el numero de instrucciones necesarias para
resolver el problema con respecto al tamano del problema, esta es la esencia de la complejidad.
Necesitamos contar las instrucciones que realiza un algoritmo. Suponemos que cada instruccion se
realiza en tiempo constante (1 Operacion Elemental).
Se considera 1 OE:
• Operaciones aritmeticas basicas
• Asignaciones a variables de tipo predefinido por el compilador
• Saltos (llamadas a funcion)
• Comparaciones logicas
• Accesos a estructuras indexadas basicas (vectores y matrices)
El tiempo de 1 OE es de orden 1
Mejor caso, peor caso
Complejidad en el peor caso (Big O): cuánto va a tardar el algoritmo como mucho, cuando n es lo
suficientemente grande
Asintotas y ordenes de complejidad
La idea de la complejidad de un algoritmo es conocer como se comporta el tiempo de ejecucion
conforme el tamano del problema va creciendo, especialmente para valores muy grandes y
especialmente en el peor de los casos.
La complejidad no se expresa como un numero sino como una funcion T(n).
Asi, la complejidad de los algoritmos esta definida por funciones.
Podemos agrupar todas las complejidades que crecen de la misma manera. A ese agrupamiento le
vamos a llamar orden de complejidad.
Esto es, para todas las funciones que agrupemos en un mismo orden, encontraremos una asíntota que
al multiplicarla por un valor nos acote a nuestra funcion superiormente cuando estemos tratando el peor
caso.
En lugar de hallar los tiempos exactos que tarda un algoritmo en solucionar uno o varios problema, lo
que analizamos es la asíntota que representa a todos los algoritmos cuyo tiempo crece de igual forma
cuando el tamano del problema tiende al infinito.
No se busca la funcion de complejidad real sino el orden al que pertenece la complejidad del
algoritmo.
Cada secuencia de instrucciones se cuenta como una sola instruccion. Lo que influye en la complejidad
son principalmente los bucles (for/while) y las condiciones (if/else) que tienen efecto sobre los bucles.
Cuando decimos que la complejidad de un algoritmo es de un orden concreto, por ejemplo de orden n 2,
podemos estar seguros de que para cualquier valor de n, aun en el peor caso, el valor que obtengamos
nunca será mayor que c*n2 , siendo c un real mayor que 1.
Orden Nombre Comentario
O(1) constante Independiente del tamano de la entrada. Ej Acceso a una posicion
de un arreglo
O(log n) Logaritmico Implica que un bucle realiza menos iteraciones que la talla del
problema. Ej. Busqueda dicotomica en un vector ordenado.
Busqueda en un arbol binario balanceado
O(n) Lineal Proporcional al tamano de la entrada n.
Ej. busqueda de un elemento en una lista ordenada o desordenada.
O(n log n) ene logaritmico Propio de tecnicas “divide y venceras” en las que el problema se
divide en partes, las que una vez resueltas se combinan los
resultados para obtener la solucion global. Algoritmos avanzados
de ordenamiento. Ej. Merge sort, Heap sort y QuickSort (este
ultimo solo en el caso promedio)
O(nc) , c > 1 Polinomico Propio de anidacion. Bucles (for/while)
O(n2) Cuadratico Caso particular del polinomico. Algoritmos basicos de
ordenamiento. ej. Burbuja, selección, insersión. Quick sort en el
peor caso.
O(n3)
O(cn) , c > 1 Exponencial Suma de recurrencias
O(2n) Numero de Fibonacci (caso particular de Exponencial)
O(n!) Factorial Permutaciones
Caso 1. Recursividad lineal (Ej. Factorial de un numero)
T(n) = T(n-1) + C_2 , n > 1
T(n) ϵ O(n)
Caso 2. Recursividad multiple (Ej. Suma de recurrencias. Nro de Fibonacci)
T(n) = 2T(n-1) + C_2 (1) n>1
T(n-1) = 2T((n-1)-1) + C_2 definición
T(n-1) = 2T(n-2) + C_2 (2)
T(n) = 2(2T(n-2) + C_2) + C_2 reemplazo (2) en (1)
T(n) = 4T(n-2) + 2C_2 + C_2
T(n) = 4T(n-2) + 3C_2
T(n) = 4(2T(n-3) + C_2) + 3C_2
T(n) = 8T(n-3) + 4C_2 + 3C_2
T(n) = 8T(n-3) + 7C_2
T(n) = 2^kT(n-k) + (2^k-1)C_2
T(n) = 2^nT(n-1) + (2^n-1)C_2 caso base n-k=1, k=n-1
T(n) = C_1 + 2^n C_2 - 1 C_2 distributiba en segundo término
T(n) ϵ O(2^n) conclusión
Caso 3. Busqueda en un arbol binario balanceado
T(n) = T(n/2) + C_2 , n > 1
T(n) ϵ O(log(n))
Ecuacion de recurrencia para traverse in order
T(n) = 2T(n/2) + C_2 , n > 1
T(n) ϵ O(n)
