Complejidad de algoritmos. Análisis de Algoritmos

Complejidad de algoritmos

Johann Ortiz Garrido

Análisis de Algoritmos

Instituto IACC

Septiembre 10 del 2018

Desarrollo

1. 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.

1. ¿Qué complejidad tiene su algoritmo? ¿Por qué?
2. ¿Es posible mejorar su rendimiento? ¿Cómo?
3. ¿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

1. 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]

1. ¿Qué complejidad tiene este algoritmo?
2. ¿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.

...