Complejidad de algoritmos. Análisis de Algoritmos
Enviado por kloex • 17 de Septiembre de 2018 • Documentos de Investigación • 342 Palabras (2 Páginas) • 190 Visitas
Complejidad de algoritmos
Johann Ortiz Garrido
Análisis de Algoritmos
Instituto IACC
Septiembre 10 del 2018
Desarrollo
- Se dice que una palabra es palíndroma cuando se lee de la misma forma hacia adelante y hacia atrás. Por ejemplo: oso, ara, arenera, anilina, radar o reconocer. Cree un algoritmo, en pseudocódigo, que reconozca cuándo una palabra es palíndroma.
- ¿Qué complejidad tiene su algoritmo? ¿Por qué?
- ¿Es posible mejorar su rendimiento? ¿Cómo?
- ¿Cómo sería un algoritmo exponencial para calcular esto?
[pic 1]
a.- Este algoritmo posee una complejidad logaritmica, ya que este tipo de algoritmos va creciendo a medida que crece la cantidad de elementos que se procesan, en este caso va a aunmentar su complejidad dependiendo de la extension de la palabra a procesar.
b.- me es dificil saber como mejorarlo, ya que se utilizo la menor cantidad de asignaciones posibles, un ciclo, una comparación, tal vez quitando la muestra del resultado al final del algoritmo.
c.- En este caso tendriamos “1” asignación en el for mas n asignaciones dentro del for, 2 comparaciones y 1 incremento.
1n+n+2+n
3n+2
- Suponga que tiene un algoritmo con un ciclo “for” anidado, es decir un ciclo “for” dentro de un ciclo “for”, como muestra el ejemplo:
[pic 2]
- ¿Qué complejidad tiene este algoritmo?
- ¿Es lineal, cuadrático, logarítmico o exponencial? ¿Por qué?
a.- El algoritmo de la imagen presenta una complejidad Cuadrática.
b.- Es cuadratico, la complejidad de este algoritmo se puede representar a traves de una función cuadratico.
En si podemos distinguir que este algoritmo tiene 2 ciclos for anidades, teniendo dentro del for interno “1” operacion que se repite n veces y que el ciclo for externo hace que se repita n veces mas y vemos que al final tiene una nueva operación que es donde muestra el resultado por pantalla. Y esto lo representariamos asi.
1 = la operacion interna.
n = la cantidad que se repite en el ciclo interior
n = la cantidad que se repite en el ciclo exterior
1 = operacion fuera del ciclo for.
Quedando de la siguiente manera:
1 * n * n + 1
1 +1[pic 3]
Bibliografía
- Apuntes de la semana 4 IACC.
...