Implementacion De Pila

Complejidad

En general, es posible realizar el estudio de la complejidad de un algoritmo sólo en base a un conjunto reducido de sentencias, aquellas que caracterizan que el algoritmo sea lento o rápido en el sentido que nos interesa.

La eficiencia de un algoritmo es una medida de lo que consume a la hora de ejecutarse: tiempo de ejecución, y memoria ocupada.

Para medirlos una forma sería la empírica: cronometrar el tiempo y analizar el uso de memoria, pero esto nos daría el resultado para un caso concreto en un PC concreto, y de poco nos sirve esto. Una medida más util es el orden de complejidad del algoritmo, que es la base del análisis de los mismos.

El orden de complejidad (o complejidad asintótica) se expresa usando la notación "O(n)", que nos dice como se relaciona el tiempo de ejecución con el tamaño de la entrada.

Eficiencia

En general, se considera que la solución de un problema es eficiente si el tiempo de ejecución está acotado por una función polinomial, es decir, por O(nk). A este tipo de se le considera un problema fácil. En caso de que su tiempo de ejecución sea mayor, se le considera difícil. Para saber si un problema es fácil, sólo debemos encontrar un algoritmo que lo resuelva en forma rápida. Para saber si un problema es difícil no basta con encontrar un algoritmo que no sea eficiente, sino que tenemos que demostrar que no existe algoritmo que lo resuelva de forma fácil. Dado que todo problema que no es fácil lo consideramos difícil, cualquier problema que se compruebe que es imposible de solucionar entra en la última categoría.

Los tiempos de ejecución más usados se ordenan de la siguiente forma (de más rápidos a más lentos): O(1) (constante), O(lgn) (logarítmico), O([lgn]k) (polilogarítmico), O(n) (lineal), O(nlgn), O(n2) (cuadrado), O(n3) (cúbico), O(nk) (polinomial), O(kn) (exponencial), O(nn) y O(n!) (factorial) donde n es la entrada y k una constante.

Calculo del algoritmo y implementación de la pila

PUSH(DATO)

SI T= MAX (`1´)

ESCRIBE (OVER FLOW)

O SI T=N (`2´)

T=MIN (`3´)

PILA(T)=DATO (`4´)

O BIEN

T=T+1 (`5´)

PILA(T)=DATO

...