Control de semana 4, analisis de algortimos, IACC

 Complejidad de algoritmos

Pedro Luis Godoy Arellano

Análisis de algoritmos

Instituto profesional IACC

21-05-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.

Algoritmo sin_titulo

    Escribir 'Ingrese la palabra'; 

    leer Palabraoriginal; 

    Para i<-Longitud(Palabraoriginal) Hasta 0 Con Paso -1 Hacer

        PalabraInvertida<-PalabraInvertida+ Subcadena(Palabraoriginal,i,i); 

    FinPara

    Limpiar Pantalla

    si PalabraInvertida = Palabraoriginal Entonces 

        Escribir "las palabras se escriben igual estando invertida como no entonces son palíndromas";

    SiNo

        Escribir "las palabras no se escriben igual estando invertida como no entonces no son palíndromas";

    FinSi

    Escribir "Palabra original",Palabraoriginal;

    Escribir "palabra volteada",PalabraInvertida;

FinProceso

Para comprobar que este código esté funcionando correctamente procedí a sacar dos screenshots  mostrando en el caso de que las palabras sean palíndromas como no.  

[pic 1]

En este caso se muestra cómo reacciona el código a ingresar una palabra que no sea palíndroma que en este caso la palabra es “conclusiones”.

[pic 2]

Este es el caso contrario donde se muestra que la palabra ingresada es palíndroma, la palabra utilizada fue “reconocer”.

1. ¿Qué complejidad tiene su algoritmo? ¿Por qué?

En la línea 1 se ingresa una variable

En la línea 3 se ingresa los valores tomando en cuenta la longitud y una subcadena

En la línea 8 se muestra una condición a realizar

En la línea 9 se muestra si la condición resultara positiva para finalizar el resultado (básicamente “true”)  

En la línea 11 se muestra un resultado en el caso de que la condición fuese negativa (básicamente “false”)

En el mejor de los casos se ejecutará la línea 9, en el caso de que la palabra ingresada se pueda escribir y leer de igual forma estando invertida o no,  esta será una palabra palíndroma y daría fin al código, en el otro caso se ejecutaría la línea 11 donde la palabra ingresada no se escribe ni se lee de igual manera dando como resultado una palabra no palíndroma.

1. ¿Es posible mejorar su rendimiento? ¿Cómo?

Yo creo que sí, se podría mejorar el rendimiento del código quizás calcular los tiempos de ejecución de los algoritmos utilizando el peor caso, es factible encontrar las funciones que acoten la ejecución, o sea, es posible encontrar una nueva función f’ que pueda acompañar a la función original debajo de esta, y se podría decir que no se demorara menos que f’.

...