Complejidad de algoritmos
Páginas: 3 (522 palabras)
Publicado: 4 de marzo de 2010
Concepto Complejidad Algoritmos
La resolución práctica de un problema exige por una parte un algoritmo o método de resolución y por otra un programa o codificación de aquel en un ordenador real.Ambos componentes tienen su importancia, pero la del algoritmo es absolutamente esencial, mientras que la codificación puede muchas veces pasar a nivel de anécdota.
A efectos prácticos oingenieriles, nos deben preocupar los recursos físicos necesarios para que un programa se ejecute.
Aunque puede haber muchos parametros, los mas usuales son el tiempo de ejecución y la cantidad dememoria (espacio).
Ocurre con frecuencia que ambos parametros están fijados por otras razones y se plantea la pregunta inversa: ¿cual es el tamano del mayor problema que puedo resolver en T segundosy/o con M bytes de memoria?
En lo que sigue nos centramos casi siempre en el parametro tiempo de ejecución, si bien las ideas desarrolladas son fácilmente aplicables a otro tipo de recursos.Para cada problema determinaremos un medida N de su tamaño (por número de datos) e intentaremos hallar respuestas en función de dicho N.
El concepto exacto que mide N depende de la naturaleza delproblema.
Así, para un vector se suele utizar como N su longitud; para una matriz, el número de elementos que la componen; para un grafo, puede ser el número de nodos (a veces es mas importanteconsiderar el número de arcos, dependiendo del tipo de problema a resolver), en un archivo se suele usar el número de registros, etc.
Es imposible dar una regla general, pues cada problema tiene supropia lógica de coste.
Tiempo de Ejecución
Una medida que suele ser útil conocer es el tiempo de ejecución de un programa en función de N, lo que denominaremos T(N).
Esta función se puedemedir físicamente (ejecutando el programa, reloj en mano), o calcularse sobre el código contando instrucciones a ejecutar y multiplicando por el tiempo requerido por cada instrucción.
Así, un...
La resolución práctica de un problema exige por una parte un algoritmo o método de resolución y por otra un programa o codificación de aquel en un ordenador real.Ambos componentes tienen su importancia, pero la del algoritmo es absolutamente esencial, mientras que la codificación puede muchas veces pasar a nivel de anécdota.
A efectos prácticos oingenieriles, nos deben preocupar los recursos físicos necesarios para que un programa se ejecute.
Aunque puede haber muchos parametros, los mas usuales son el tiempo de ejecución y la cantidad dememoria (espacio).
Ocurre con frecuencia que ambos parametros están fijados por otras razones y se plantea la pregunta inversa: ¿cual es el tamano del mayor problema que puedo resolver en T segundosy/o con M bytes de memoria?
En lo que sigue nos centramos casi siempre en el parametro tiempo de ejecución, si bien las ideas desarrolladas son fácilmente aplicables a otro tipo de recursos.Para cada problema determinaremos un medida N de su tamaño (por número de datos) e intentaremos hallar respuestas en función de dicho N.
El concepto exacto que mide N depende de la naturaleza delproblema.
Así, para un vector se suele utizar como N su longitud; para una matriz, el número de elementos que la componen; para un grafo, puede ser el número de nodos (a veces es mas importanteconsiderar el número de arcos, dependiendo del tipo de problema a resolver), en un archivo se suele usar el número de registros, etc.
Es imposible dar una regla general, pues cada problema tiene supropia lógica de coste.
Tiempo de Ejecución
Una medida que suele ser útil conocer es el tiempo de ejecución de un programa en función de N, lo que denominaremos T(N).
Esta función se puedemedir físicamente (ejecutando el programa, reloj en mano), o calcularse sobre el código contando instrucciones a ejecutar y multiplicando por el tiempo requerido por cada instrucción.
Así, un...
Leer documento completo
Regístrate para leer el documento completo.