La implementación es el proceso que toma la especificación del algoritmo y la traduce
a una forma que pueda aplicarse a la solución del problema para el cual fue diseñado.
La implementación puede tomar formas muy diversas: podría significar la construcción
de un circuito eléctrico o de un dispositivo mecánico que cumpla con las condiciones
especificadas. Pero restrinjamos la definición al campo de la informática:
en este sentido, implementar significa traducir el algoritmo a un lenguaje que pueda
ser interpretado por un motor de ejecución.
Para el análisis y estudio de los algoritmos usualmente se utiliza una forma abstracta
de implementación, la cual no utiliza un lenguaje de programación específico, sino
que emplea formas de representar el algoritmo que luego pueden ser directamente
traducidas a un lenguaje en particular. Algunas de estas formas son los diagramas
de flujo, los diagramas de bloques y el seudo código. Este último es “casi”
un lenguaje imperativo, con la salvedad de que no toma en cuenta los tipos de datos
y, además, sus instrucciones pueden estar en idioma español o en cualquier otro,
ya que no serán interpretadas por ninguna computadora.
Un sencillo ejemplo de la implementación en seudo código de nuestro algoritmo
BuscarMaximo sería la siguiente:
Función BuscarMaximo(lista)
Mayor = lista(1)
Contador = 2
Mientras Contador ? longitud(lista) hacer
Si lista(Contador) > Mayor entonces
Mayor = lista(Contador)
Fin Si
Contador = Contador + 1Fin Mientras
Devolver Mayor
Fin Función
Eficiencia de los algoritmos
La especificación de un algoritmo puede incluir consideraciones sobre su eficiencia,
dado que una implementación incorrecta puede hacer que demore en ejecutarse
mucho más tiempo de lo aceptable. Para ello se utilizan notaciones que expresan la
complejidad de los algoritmos en función del volumen de datos a procesar (ver el
Capítulo 4 para mayor información). Una de estas notaciones es la denominada “la
gran O”, que indica la cantidad de veces que el algoritmo debe repetir su bloque
principal de instrucciones para hacer su trabajo.
El ciclo principal del algoritmo BuscarMaximo –explicado en la página 20– recorre
una vez toda la lista de n elementos para determinar cuál es el mayor. Su bloque
principal (el delimitado entre Mientras y Fin Mientras) se repite tantas veces como
elementos haya en la lista. Por lo tanto, se dice que su complejidad es O(n) o que
tiene complejidad lineal, ya que el tiempo que demora en ejecutarse el algoritmo
aumentará proporcionalmente a la cantidad de elementos que tenga la lista.