Control 4, ANÁLISIS DE ALGORITMOS, IACC
Enviado por kaosho • 16 de Junio de 2019 • Tarea • 871 Palabras (4 Páginas) • 334 Visitas
Complejidad de algoritmos.
_
ANÁLISIS DE ALGORITMOS
Instituto IACC
02-02-2019
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.
[pic 1]
Algoritmo en Pseudocódigo |
Algoritmo palindroma Definir p1, p2 Como Caracter Escribir "Escriba una palabra : " Leer p1 Para i = Longitud(p1) Hasta 1 Con Paso -1 Hacer p2 = Concatenar(p2,SubCadena(p1,i,i)) FinPara Si Mayusculas(p1) = Mayusculas(p2) Entonces Escribir "La palabra es Palindroma" SiNo Escribir "La palabra NO es palindroma" FinSi FinAlgoritmo |
- Resultados ejecución de pseudocódigo en PSeInt, con palabra “oso”,”reconocer” y “mala”
[pic 2]
[pic 3]
[pic 4]
- ¿Qué complejidad tiene su algoritmo? ¿Por qué?
Tiene una complejidad Lineal, ya que la entrada es una palabra, es decir un conjunto de caracteres, que son recorrido solo una vez para organizarlos de manera inversa y camparlo a como entro la palabra, además la palabra es solo ingresada una vez.
- ¿Es posible mejorar su rendimiento? ¿Cómo?
Opino que su rendimiento puede ser mejorable, planteando el algoritmo de otra manera, como comparando las letras de cada extremo, lo cual puede entregar una respuesta rápida para los casos que las palabras no son palíndromas, ya que en el algoritmo desarrollado se ordena la palabra en un variable desde atrás hacia adelante y se compara con la palabra, entonces para casos de palabra muy largas, siempre se tendrá que realizar un bucle para ordenar la palabra de manera inversa.
[pic 5]
Segundo algoritmo en Pseudocódigo |
Algoritmo palindroma_mejora2 Definir palabra, respuesta Como Caracter Definir d, i Como Entero Escribir "Escriba una palabra : " Leer palabra i = Longitud(palabra) d = 1 respuesta = "SI" Repetir Si SubCadena(palabra,d,d) != SubCadena(palabra,i,i) entonces respuesta = "NO" d = i SiNo d = d + 1 i = i - 1 FinSi Hasta Que d = i Escribir "La palabra es "+respuesta+" es palindroma" FinAlgoritmo |
- ¿Cómo sería un algoritmo exponencial para calcular esto?
Los algoritmos de este tipo de complejidad son los que crecen en forma exponencial con la cantidad de elementos que son analizados. Un algoritmo exponencial para este caso, se podría llevar a cabo realizando uno que permita comparar varias palabras a la vez.
- 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 6]
- ¿Qué complejidad tiene este algoritmo?
El algoritmo del ejemplo, tiene dos bucles anidados, en donde cada bucle se ejecuta n veces, y el bucle interior, también se ejecutará n veces, entonces la complejidad del algoritmo seria: [pic 7]
...