Uno de los grandes problemas que se presentan es cuando el algoritmo tiene que tomar una decisión. Los problemas se clasifican en conjuntos de complejidad llamadas clases de complejidad.

CLASE DE COMPLEJIDAD P

Es el conjunto de problemas de decisión que pueden ser resueltos en tiempo polinomico calculando a partir de la entrada a una maquina de turing determinista y que corresponde a problemas que puede ser resuelto a un en el peor de los casos

Ej. Conocer un número primo.

CLASE DE COMPLEJIDAD NP

NO PROCESABLE

Es el conjunto de problemas de decisión que pueden ser resuelto por una marina de turing no determinista en tiempo polinomico las cuales tienen la propiedad de que su solución puede ser verificada.

CLASE DE COMPLEJIDAD NP COMPLETO

Es el conjunto de problemas de dedición en NP que destacan por su extrema complejidad y que decimos que se encuentran en la frontera externa de la clase NP.

NOTACION ASINTONICA O GRANDE

Se utilizan para hace referencia para la velocidad de crecimiento de los valores de una función, es decir, su utilidad radica en encontrar su limite superior de tiempo de ejecución de un algoritmo en el peor de los casos.

La O

Es una función g(n) pertenece a O(f (n))

Rotacion asintótica “OMEGA”

Se utiliza para especificar una cosa inferior o la velocidad

Tiempo de ejecución del algoritmo

El riempo de ejecución de un programa en función de n (definición de datos) se denimina T(n)