Concepto de complejidad de algoritmos
Páginas: 2 (339 palabras)
Publicado: 28 de diciembre de 2010
1.1 Concepto de complejidad de algoritmo
La complejidad (o costo) de un algoritmo es una medida de la cantidad de recursos (tiempo, memoria) que el algoritmo necesita. La complejidad de unalgoritmo se expresa en función del tamaño (o talla) del problema.
La función de complejidad tiene como variable independiente el tamaño del problema y sirve para medir la complejidad (espacial otemporal). Mide el tiempo/espacio relativo en función del tamaño del problema.
El comportamiento de la función determina la eficiencia. No es única para un algoritmo: depende de los datos. Para un mismotamaño del problema, las distintas presentaciones iníciales de los datos dan lugar a distintas funciones de complejidad. Es el caso de una ordenación si los datos están todos inicialmente desordenados,parcialmente ordenados o en orden inverso.
Ejemplo:
f(n)= 3n2+2n+1 , en donde n es el tamaño del problema y expresa el tiempo en unidades de tiempo.
Es la parte de la teoría de lacomputación que estudia los recursos requeridos durante el cálculo para resolver un problema los cuales se dividen en: el tiempo y el espacio.
Los problemas de decisión se clasifican en conjuntos decomplejidad llamadas clases de complejidad:
- Clase de complejidad P:
Es el conjunto de los problemas de decisión que puedan ser resueltos en tiempo polinómico calculado a partir de la entrada por unamaquina de turing determinista y que corresponde a problemas que pueden ser resueltos aun en el peor de sus casos.
Ejemplo:
1. Saber si un número entero es primo.
2. Saber si una frasepertenece a un conjunto de frases.
- Clase de complejidad NP:
Es el conjunto de los problemas de decisión que pueden ser resueltos por una maquina de turing no determinista en tiempo polinómico lascuales tienen la propiedad de que su solución puede ser verificada.
- Clase de complejidad NP-Completo:
Es el subconjunto de los problemas de decisión en NP que destacan por su extrema...
La complejidad (o costo) de un algoritmo es una medida de la cantidad de recursos (tiempo, memoria) que el algoritmo necesita. La complejidad de unalgoritmo se expresa en función del tamaño (o talla) del problema.
La función de complejidad tiene como variable independiente el tamaño del problema y sirve para medir la complejidad (espacial otemporal). Mide el tiempo/espacio relativo en función del tamaño del problema.
El comportamiento de la función determina la eficiencia. No es única para un algoritmo: depende de los datos. Para un mismotamaño del problema, las distintas presentaciones iníciales de los datos dan lugar a distintas funciones de complejidad. Es el caso de una ordenación si los datos están todos inicialmente desordenados,parcialmente ordenados o en orden inverso.
Ejemplo:
f(n)= 3n2+2n+1 , en donde n es el tamaño del problema y expresa el tiempo en unidades de tiempo.
Es la parte de la teoría de lacomputación que estudia los recursos requeridos durante el cálculo para resolver un problema los cuales se dividen en: el tiempo y el espacio.
Los problemas de decisión se clasifican en conjuntos decomplejidad llamadas clases de complejidad:
- Clase de complejidad P:
Es el conjunto de los problemas de decisión que puedan ser resueltos en tiempo polinómico calculado a partir de la entrada por unamaquina de turing determinista y que corresponde a problemas que pueden ser resueltos aun en el peor de sus casos.
Ejemplo:
1. Saber si un número entero es primo.
2. Saber si una frasepertenece a un conjunto de frases.
- Clase de complejidad NP:
Es el conjunto de los problemas de decisión que pueden ser resueltos por una maquina de turing no determinista en tiempo polinómico lascuales tienen la propiedad de que su solución puede ser verificada.
- Clase de complejidad NP-Completo:
Es el subconjunto de los problemas de decisión en NP que destacan por su extrema...
Leer documento completo
Regístrate para leer el documento completo.