Teoría de la complejidad Algorítmica

Teoría de la complejidad Algorítmica

En la ciencia de la computación los algoritmos son más importantes que los LP o que las computadoras; la solución de un problema haciendo uso de las computadoras requiere por una parte un algoritmo o método de resolución y por otra un programa o codificación del algoritmo en un LP. Ambos componentes tienen importancia; pero la del algoritmo es absolutamente indispensable; sabemos que un algoritmo es una secuencia de pasos para resolver un problema, sus características son:

1. Independiente: Del LP y de la máquina.
2. Definido: De pasos claros y concretos.
3. Finito: En el número de pasos que usará.
4. Preciso: Cada paso arroja un cálculo correcto.
5. Recibe datos: Debe poseer datos de entrada. 

COMPLEJIDAD ALGORÍTMICA

• Un algoritmo será mas eficiente comparado con otro, siempre que consuma menos recursos, como el tiempo y espacio de memoria necesarios para ejecutarlo.
• La eficiencia de un algoritmo puede ser cuantificada con las siguientes medidas de complejidad:

Complejidad Temporal o Tiempo de ejecución: Tiempo de cómputo necesario para ejecutar algún programa. 

 

Complejidad Espacial: Memoria que utiliza un programa para su ejecución, 

La eficiencia en memoria de un algoritmo indica la cantidad de espacio requerido para ejecutar el algoritmo; es decir, el espacio en memoria que ocupan todas las variables propias al algoritmo. Para calcular la memoria estática de un algoritmo se suma la memoria que ocupan las variables declaradas en el algoritmo. Para el caso de la memoria dinámica, el cálculo no es tan simple ya que, este depende de cada ejecución del algoritmo.

• Este análisis se basa en las Complejidades Temporales, con este fin, para cada problema determinaremos una medida N, que llamaremos tamaño de la entrada o número de datos a procesar por el programa, intentaremos hallar respuestas en función de dicha N.
• El concepto exacto que cuantifica N dependerá de la naturaleza del problema, si hablamos de un array se puede ver a N como el rango del array, para una matriz, el número de elementos que la componen; para un grafo, podría ser el número de nodos o arcos que lo arman, no se puede establecer una regla para N, pues cada problema acarrea su propia lógica y complejidad.

Órdenes de Complejidad

• La familia O(f(n)) define un Orden de Complejidad. Elegiremos como representante de este Orden de Complejidad a la función f(n) más sencilla perteneciente a esta familia.
• Las funciones de complejidad algorítmica más habituales en las cuales el único factor del que dependen es el tamaño de la muestra de entrada n, ordenadas de mayor a menor eficiencia son:

O(1)	Orden constante
O(log n)	Orden logarítmico
O(n)	Orden lineal
O(n log n)	Orden cuasi-lineal
O(n2)	Orden cuadrático
O(n3)	Orden cúbico
O(na)	Orden polinómico
O(2n)	Orden exponencial
O(n!)	Orden factorial

• Se identifica una Jerarquía de Ordenes de Complejidad que coincide con el orden de la tabla mostrada; jerarquía en el sentido de que cada orden de complejidad inferior tiene a las superiores como subconjuntos.
• • 
    
  • O(1): Complejidad constante. Cuando las instrucciones se ejecutan una vez.
  • O(log n): Complejidad logarítmica. Esta suele aparecer en determinados algoritmos con iteración o recursión no estructural, ejemplo la búsqueda binaria.
  • O(n): Complejidad lineal. Es una complejidad buena y también muy usual. Aparece en la evaluación de bucles simples siempre que la complejidad de las instrucciones interiores sea constante.
  • O(n log n): Complejidad cuasi-lineal. Se encuentra en algoritmos de tipo divide y vencerás como por ejemplo en el método de ordenación quicksort y se considera una buena complejidad. Si n se duplica, el tiempo de ejecución es ligeramente mayor del doble.
  • O(n2): Complejidad cuadrática. Aparece en bucles o ciclos doblemente anidados. Si n se duplica, el tiempo de ejecución aumenta cuatro veces.
  • O(n3): Complejidad cúbica. Suele darse en bucles con triple anidación. Si n se duplica, el tiempo de ejecución se multiplica por ocho. Para un valor grande de n empieza a crecer dramáticamente.
  • O(na): Complejidad polinómica (a > 3). Si a crece, la complejidad del programa es bastante mala.
  • O(2n): Complejidad exponencial. No suelen ser muy útiles en la práctica por el elevadísimo tiempo de ejecución. Se dan en subprogramas recursivos que contengan dos o más llamadas internas. N
  
  Enlaces para el material =(PDF)=: Link Seguro, Links Alternativo.
  Fuente: Monografias
  Paginas relacionadas: Literaturas y otras cuestiones morales, Ceo Developers, Geniality Software.
  
  Nota: Si el material te ha servido de ayuda por favor comparte el post, necesitamos que aumente el numero de personas que conocen acerca de estos temas, estamos en la revolucion informatica y todos debemos poner un poco de nuestra parte, para que este movimiento nunca muera. Unidos por la informatica.