Complejidad Computacional

 

¿Qué es Complejidad?

 

 

Complejidad T(n) = número de operaciones elementales en función de la medida n, hace referencia al peor caso.

Se entiende como el número de operaciones necesarias que debe realizar un algoritmo para resolver un determinado problema.

 

¿Cómo se mide la complejidad?

 

 

Se mide  de acuerdo a Cantidad de operaciones en función del tamaño de la Entrada (n), se denota por la notación asintótica correspondiente a la complejidad asociada.

 

¿Que es la notación asintótica?

 

 

La notación que determina la complejidad de un algoritmo es la notación asintótica, ésta es la notación propuesta por la comunidad científica para describir el comportamiento en eficiencia o complejidad de un algoritmo.

 

¿La complejidad está asociada a un problema o a una solución del problema?

 

 

La complejidad computacional  esta asociada al problema no a la solución, a mayor problema mayor complejidad del algoritmo.

 

¿La complejidad depende de la implementación?

 

 

NO, la complejidad de un algoritmo esta dada por el tamaño del problema a resolver, la eficiencia del algoritmo esta dada por la implementación del algoritmo para resolver el problema, considerando tiempo, memoria, líneas de código, bucles utilizados, cantidad de procesadores, etc.

 

¿Qué se entiende por complejidad?

 

 

La Complejidad es una medida de la cantidad que consume un algoritmo de un recurso determinado.

 

Órdenes de Complejidad.

 

O(1)	Constante
O(n)	Lineal
O(n2)	Cuadrático
O(n3)	Cúbico
O(nm)	Polinomio
O(log(n))	Logarítmico
O(nlog(n))	nlog(n)
O(mn)	Exponencial
O(n!)	Factorial

 

Casos de Complejidad.

 

 

Complejidad del PEOR CASO.

Por complejidad del peor caso entendemos el mayor número de operaciones necesarias para resolver un problema.

Complejidad del CASO PROMEDIO.

Por complejidad de caso promedio entendemos que es el número promedio de operaciones realizadas para solucionar un problema considerando todas las posibles entradas de un tamaño determinado.

Complejidad del MEJOR CASO.

Por complejidad del mejor caso entendemos el menor número de operaciones necesarias para resolver un problema.