Complejidad y Tratabilidad

Inteligencia Artificial

Complejidad y Tratabilidad

DefinidoFinitoPrecisoIndependiente

Características de un algoritmo

Ejecutar los algoritmos en un computador y medir la velocidad en segundos y el consumo de memoria en bytes.

PRUEBAS DE EVALUACIÓN

INTRATABILIDAD

Cuando a una computadora se le dificulta poder resolver un problema, se dice que el problema es intratable.Un problema es intratable si el tiempo necesario para la resolución de casos particulares de un problema crece exponencialmente con el tamaño de dichos casos.

Criterio Asintótico

Es un análisis que depende la implementación del algoritmo en un programa y es independiente de la máquina y el lenguaje.

ANALISIS ASINTÓTICO

Peor caso: Se analizan los casos donde los datos de entrada hacen que el algoritmo tarde mayor tiempo y aumentan la cantidad de trabajo.Mejor caso: Se analizan los casos donde los datos de entrada hacen que el algoritmo tarde el menor tiempo posible y disminuyen la cantidad de trabajo.Caso promedio: Se analizan los casos con los datos que se ingresan con mayor frecuencia y producen el trabajo promedio del algoritmo.

ANALISIS ASINTÓTICO

Tambien llamado Notación Asintótica o Complejidad Asintótica.El primer paso del análisis es abstraer la entrada, para encontrar algún parámetro o parámetros que caractericen el tamaño de la entrada. El segundo paso es abstraer la implementación, para encontrar alguna medida que refleje el tiempo de ejecución del algoritmo, pero que no esté ligado a un compilador o computador en particular.Esto podría ser o midiendo el número de sumas, asignaciones, referencias a arrays y bifurcaciones ejecutadas por el algoritmo.

ANALISIS ASINTÓTICO

Una caracterización del número total de pasos del algoritmo como una función del tamaño de la entrada se la llama T(n).Problemas:Es extraño encontrar un parámetro como n que caracterice completamente el número de pasos realizados por el algoritmo.El segundo problema es que los algoritmos tienden a resistirse al análisis exacto.Es necesario replegarse a una aproximación.

ANALISIS ASINTÓTICO

T(n) es O( f (n)) si T(n) < k f (n) para algunos k, para todo n > n0.La notación O( ) nos proporciona lo que llamamos un análisis asintótico.La notación O( ) abstrae los factores constantes, lo cual facilita su utilización, aunque de forma menos precisa, que la notación T( ).

Un algoritmo es eficiente si consume una menor cantidad de recursos en comparación con otros algoritmos. Los recursos que son utilizados para hacer la comparación son el tiempo y espacio de memoria necesarios para ejecutar el algoritmo.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.

Complejidad del algoritmo

Calculo de la eficiencia

A cada una de las intrucciones del algoritmo se le asigna un costo.

• Instrucciones básicas

• Secuencia de instrucciones

• Condicionales

• Iteraciones

indice=0 -> 1indice<n -> n+1indice++ -> ncout<<indice<<" "; -> (1)nT(n)= 1+(n+1)+n+(1)nT(n)=3n+2

CALCULO DE EFICIENCIA

Orden factorial

O(n!)

Orden exponencial

O(2^n)

Orden polinómico

O(n^a)

Orden cúbico

O(n^3)

Orden cuasi-lineal

O(n log n)

Orden logarítmico

O(log n)

Orden cuadrático

O(n^2)

Orden lineal

O(n)

Orden constante

O(1)

ORDENES DE COMPLEJIDAD

Orden de complejidad