Analisis de algoritmos
Páginas: 6 (1321 palabras)
Publicado: 26 de agosto de 2010
UNIDAD 1.
ANALISIS DE ALGORITMOS
OBJETIVO EDUCACIONAL. El estudiante comprenderá el concepto de complejidad de los algoritmos y su aplicación en la selección de los mismos.
1.1 CONCEPTO DE COMPLEJIDAD DE ALGORITMOS.
La mayoría de los algoritmos tienen un parámetro primario N, normalmente el número de elementos de datos a procesar, que afecta muy significativamente al tiempo deejecución. El parámetro N podría ser el grado de un polinomio, el tamaño de un archivo a ordenar o en el que se va a realizar una búsqueda, el número de nodos de un grafo, etc.
Funciones de complejidad de algoritmos más comúnmente consideradas:
Un “orden de complejidad” se define como un conjunto de funciones que comparten un mismo comportamiento asintótico. Habitualmente estos conjuntos sedenominan O (o grande).
Para cada uno de estos conjuntos se suele identificar un miembro f(n) que se utiliza como representante de la clase, hablándose del conjunto de funciones “g” que son del orden de “f(n)”. Sean “g(n)” diferentes funciones que determinan el uso de recursos (es decir, “familias” de funciones).
Prácticamente, todos los algoritmos tienen un tiempo de ejecución proporcional auna de las siguientes funciones:
|FUNCION |TIEMPO DE EJECUCION |COMPLEJIDAD |CARACTERISTICAS |DONDE SE APLICAN |SI SE DUPLICA N |
| | |O(1) |Es la más deseada. |Aparece en algoritmos sin bucles.| |
| | ||La mayor parte de las instrucciones se |Problemas analíticos o directos, | |
|1 |Constante | |ejecutan una vez o muy pocas veces. |instrucciones simples, accesos | |
| | | |La solución del problema es |indexados,comparaciones, etc. | |
| | | |independiente de N. | | |
| | |O(log(n)) |El tiempo de ejecución es más lento |En programas que resuelven un |Log N crece de forma|
| || |cuando crece N. La base del logaritmo |problema de gran tamaño |constante, pero no |
| | | |cambia ligeramente la constante. |transformándolo en uno más |se duplica hasta que|
| | | |Es una complejidad óptima. El problema|pequeño. |N llegue a N2. |
|Log N |Logarítmico | |se divide en sub-problemas una fracción | | |
| | | |más pequeños. Por ejemplo, cada vez la | | |
| || |mitad mas pequeños. | | |
| | |O(n) |Para cada elemento de entrada, se |En algoritmos que deben procesar |Se duplica el valor |
| | | |realiza una pequeña cantidad de|N entradas o N salidas. |de N. |
|N |Lineal | |procesos. | | |
| | | |Es muy buena y muy usual. Todos los | | |
|...
ANALISIS DE ALGORITMOS
OBJETIVO EDUCACIONAL. El estudiante comprenderá el concepto de complejidad de los algoritmos y su aplicación en la selección de los mismos.
1.1 CONCEPTO DE COMPLEJIDAD DE ALGORITMOS.
La mayoría de los algoritmos tienen un parámetro primario N, normalmente el número de elementos de datos a procesar, que afecta muy significativamente al tiempo deejecución. El parámetro N podría ser el grado de un polinomio, el tamaño de un archivo a ordenar o en el que se va a realizar una búsqueda, el número de nodos de un grafo, etc.
Funciones de complejidad de algoritmos más comúnmente consideradas:
Un “orden de complejidad” se define como un conjunto de funciones que comparten un mismo comportamiento asintótico. Habitualmente estos conjuntos sedenominan O (o grande).
Para cada uno de estos conjuntos se suele identificar un miembro f(n) que se utiliza como representante de la clase, hablándose del conjunto de funciones “g” que son del orden de “f(n)”. Sean “g(n)” diferentes funciones que determinan el uso de recursos (es decir, “familias” de funciones).
Prácticamente, todos los algoritmos tienen un tiempo de ejecución proporcional auna de las siguientes funciones:
|FUNCION |TIEMPO DE EJECUCION |COMPLEJIDAD |CARACTERISTICAS |DONDE SE APLICAN |SI SE DUPLICA N |
| | |O(1) |Es la más deseada. |Aparece en algoritmos sin bucles.| |
| | ||La mayor parte de las instrucciones se |Problemas analíticos o directos, | |
|1 |Constante | |ejecutan una vez o muy pocas veces. |instrucciones simples, accesos | |
| | | |La solución del problema es |indexados,comparaciones, etc. | |
| | | |independiente de N. | | |
| | |O(log(n)) |El tiempo de ejecución es más lento |En programas que resuelven un |Log N crece de forma|
| || |cuando crece N. La base del logaritmo |problema de gran tamaño |constante, pero no |
| | | |cambia ligeramente la constante. |transformándolo en uno más |se duplica hasta que|
| | | |Es una complejidad óptima. El problema|pequeño. |N llegue a N2. |
|Log N |Logarítmico | |se divide en sub-problemas una fracción | | |
| | | |más pequeños. Por ejemplo, cada vez la | | |
| || |mitad mas pequeños. | | |
| | |O(n) |Para cada elemento de entrada, se |En algoritmos que deben procesar |Se duplica el valor |
| | | |realiza una pequeña cantidad de|N entradas o N salidas. |de N. |
|N |Lineal | |procesos. | | |
| | | |Es muy buena y muy usual. Todos los | | |
|...
Leer documento completo
Regístrate para leer el documento completo.