NP contra P - Parte 2: Eficiencia

En la entrada anterior pudimos ver un ejemplo fácil de como el estudio de la algoritmia es crucial a la hora de resolver problemas que surgen en la vida cotidiana, ya sean de naturaleza logística, financiera,..., e incluso aquellos planteados a modo de mejorar nuestra calidad de vida. Véase que, por ejemplo, para una destacada empresa de transportes, el hecho de que su sistema logístico cargue los camiones con cajas de la forma más óptima o no, es algo en lo que no deben escatimar debido a las pérdidas económicas que podría suponer, [...]
En éste capítulo hablaré de modo meramente introductivo sobre el análisis de la eficiencia de los algorítmos que permite, entre otras cosas (la cuál es en cierto modo su finalidad), conseguir que una determinada aplicación que maneje tales algorítmos pueda calificarse de eficiente, visto siempre desde el punto de vista económico. Empezaremos pues por ver que es eso de la "eficiencia de los algoritmos":



En el párrafo anterior decia que la eficiencia es dinero. Es muy bien sabido que el "tiempo también es dinero". Luego aplicando la lógica: "El tiempo es eficiencia". Bien, bueno..., esto puede resultar engañoso, puesto que no es en su totalidad un razonamiento cierto. Lo mismo ocurre con mucha gente cuando se quiere comprar un ordenador: -"Pues el mío es un Pentium IV 1,5GHz y puesto que tu tienes un 1,3GHz el mío es mejor"-, cuando la medición del rendimiento en este caso depende mucho más de otros factores, como por ejemplo, el factor de escalaridad de la máquina que es la función inversa de los "ciclos de reloj" en los que se ejecuta una determinada instrucción de algún programa informático (CPI). Volviendo al caso diré que el algorítmo más eficiente es aquél que mantiene una relación favorable entre los recursos consumidos y los productos obtenidos. Cuando hablo de recursos consumidos me refiero al tiempo por supuesto, pero también(en cuanto a una máquina se refiere) a la memoria disponible, la gestión de entrada-salida(E/S),... Estos "recursos" dependen de dos tipos de factores:

• Factores internos: Básicamente dependen del tamaño de la entrada del problema y la naturaleza de los datos de dicha entrada. Cuando hablamos de "entrada del problema" nos referimos a aquella estructura de datos que queremos modificar; es decir, si suponemos que el problema consiste en ordenar por edades a un conjunto de alumnos de una clase, dicho conjunto de alumnos(donde el conjunto sería la estructura de datos a manejar) sería la entrada de nuestro problema. Tras aplicar el algoritmo, la salida sería el mismo conjunto pero ya ordenado.
  La naturaleza de los datos de entrada viene a decirnos cómo están predispuestos tales datos inicialmente. Esto es importante ya que podemos averiguar el mejor y el peor caso. Para verlo, en el ejemplo anterior, si inicialmente tenemos el conjunto de alumnos ordenado ya de por sí, la solución del problema es trivial y da como salida la entrada sin modificar; luego se trataría del mejor de los casos. Por el contrario, si el primero de la lista inicial es el último que queremos en la lista y así sucesivamente, estaríamos en el peor de los casos.
• Factores Externos: Dependen del tipo de ordenador, del lenguaje de programación y de la implementación. Estos factores no aportan información sobre el algorítmo.
  

Los factores externos son aquellos que se pasan por alto a la hora de evaluar algorítmos. Esto es porque un mismo algoritmo puede ser implementado en diversas máquinas y/o haciendo uso de diferentes lenguajes para programarlo. Este aspecto se omite poniendo en juego una unidad elementar que mide la eficiencia sin tener en cuenta los factores externos. A esta unidad la llamaremos "operación elemental". El tiempo de ejecución de una de estas operaciones se puede acotar superiormente por una constante que sólamente dependerá de la implementación particular usada (máquina, lenguaje de programación...). De esta manera la constante no dependerá ni del tamaño ni de los diversos parámetros de nuestro problema en cuestión. Luego, sólo el número de operaciones elementales ejecutadas importará en el análisis, y no el tiempo exacto requerido por cada una de ellas.

Para explicar todo esto de forma gráfica nada mejor que un ejemplo. Propongamos el de antes:
Tenemos un grupo de alumnos en una clase y queremos ordenarlos por edades. La estructura de datos podríamos considerarla como un vector o "array" de elementos. Cada elemento lo forma un alumno que a su vez sería otra estructura que contendría, entre otros, un campo "edad" que se trataría como un número natural(con una relación de orden total). Realmente, esto anterior no nos atañe, ya que como dijimos antes, todo ello dependerá del lenguaje de programación que usemos pero, aún así, necesitamos saber que tipo de estructuras estamos manejando ya que son las entradas de nuestros algorítmos. Nos interesa sobre todo el "análisis del algoritmo" y en este caso y como comenté en el apartado anterior, ello dependerá de evaluar su eficiencia en el peor de los casos, o lo que es lo mismo, calcular la complejidad del algorítmo.
El análisis se realiza mediante conteo de operaciones elementales. Cada linea de programa asociado al algorítmo tendrá un número determinado de estas operaciones. Si sumamos todas las operaciones de todas las líneas cuando corremos el programa en el que los datos de entrada reflejan el peor de los casos, el resultado será (siempre en función del tamaño que viene dado por un numero "n") lo que nos diga la eficiencia de nuestro algorítmo.
Para el ejemplo anterior podemos usar el algorítmo burbuja:



¿Cuál es la complejidad de este algorítmo, o lo que es lo mismo podríamos decir que es eficiente?



Fuente: Análisis y diseño de algoritmos: un enfoque teórico y práctico. José Ignacio Peláez Sánchez




Categoría: informatica