INSTITUO TECNOLOGICO SUPERIOR DE MISANTLA

NUEVAS TECNICAS DE OPTIMIZACION
PROGRAMACION DE SISTEMAS
Francisco Cardoso Torres instituto tecnológico superior de misantla

INDICE

Introducción 1 Cómo elegir buenos algoritmos. 2 Notaciones asintóticas más utilizadas: 3 Órdenes de magnitud más frecuentes 4 Primer algoritmo: fuerza bruta. 5 Segundo algoritmo: búsqueda dicotómica o binaria 5 Cuándo y cómo optimizar 6 Técnicas de optimización de código 8 Elimina código innecesario 9 Saca código de los bucles 9 Pasar objetos por referencia mejor que por valor 9 Minimiza y optimiza el acceso a disco 10 Referencias: 14

Introducción

"La raíz de todos los males es la optimización prematura." - D. Knuth

La …ver más…

| "Eficientes" | Θ(nk) | Polinómico | Característico de estructuras de datos lineales, como los vectores, y en los bucles. | Tratables | Θ(kn)
Θ(n!) | Exponencial | Es el peor caso. Aparece en algoritmos que se basan en el ensayo reiterado de soluciones, como los programas de descifrado de contraseñas. | Intratables |

Son deseables los algoritmos con un ritmo de crecimiento bajo. El análisis de complejidad de los algoritmos puede ser trivial en algunos casos, y extraordinariamente complicado en otros casos.
Tras este rollo teórico, calcularemos la complejidad temporal(por ser la que mayor importancia suele tener) de un algoritmo muy sencillo, para poder aplicar los conceptos presentados hasta ahora
Búsqueda de un elemento en un vector ordenado.
Primer algoritmo: fuerza bruta.
Este algoritmo no necesita de explicación, ahi va el código en C++: bool encontrado = false; const int busco; // elemento buscado const int KMAX; // longitud del vector int vector[KMAX];

for(i=0;vector[i]!=busco && i < KMAX ; i++);

if(i!=KMAX) encontrado=true; |

Análisis. Número de iteraciones del bucle:
Mejor caso: 1
Peor caso: KMAX
Caso medio: (KMAX+1)/2
En el peor caso(el elemento buscado está al final del vector), tendremos que hacer un total de n comparaciones(donde n es la longitud del vector). Tenemos pues que el tiempo que tarda el algoritmo en completarse crece linealmente en funcion del tamaño de la entrada de