ClubEnsayos.com - Ensayos de Calidad, Tareas y Monografias
Buscar

Control 4, ANÁLISIS DE ALGORITMOS, IACC


Enviado por   •  16 de Junio de 2019  •  Tareas  •  871 Palabras (4 Páginas)  •  285 Visitas

Página 1 de 4

Complejidad de algoritmos.

_

ANÁLISIS DE ALGORITMOS

Instituto IACC

02-02-2019


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.

[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]

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

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

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

  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 6]

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

...

Descargar como (para miembros actualizados)  txt (3.6 Kb)   pdf (371.3 Kb)   docx (680.2 Kb)  
Leer 3 páginas más »
Disponible sólo en Clubensayos.com