Complejidad algorítmica

    Como ya habíamos afirmado en el artículo sobre la medición de la complejidad, un algoritmo se puede clasificar en cuando a su eficiencia o coste en una de la siguientes categorías. De mayor eficiencia a menor, siendo n el tamaño del problema a tratar:

* Complejidad constante (la mejor y objetivo a buscar) O(1)
* Complejidad logarítmica (muy buena) O(log n)
* Complejidad lineal O(n)
* Complejidad lineal*logarítmica O(n log n)
* Complejidad cuadrática O(n²)
* Complejidad polinomial (mala) O(n^a) con a>2
* Complejidad exponencial (muy mala) O(aⁿ) con a>2
* Complejidad factorial (la peor, problemas generalmente intratables) O(n!)

    Tenemos pues que en cuanto a complejidad algorítmica:

1 << log n << n << nlog n << n² << n³ << ... << 2ⁿ << n!

    A menor orden menos recursos se necesitarán para llevar a cabo la resolución del problema, menor coste.

    Lo que nos puede interesar a continuación es obtener un conjunto de reglas prácticas que no sirvan para determinar la complejidad de un algoritmo y así por ejemplo poder comparar varios algoritmos y determinar cual es el mejor. Estas reglas no pueden por desgracia, tras seguirlas detenidamente, llevarnos a determinar con exactitud el coste de un algoritmo pero son útiles para ayudarnos en este empeño.

    Estas reglas deben tener en consideración los costes de:

*Instrucciones simples
*Composición de instrucciones
*Instrucciones de selección
*Bucles
*Subprogramas

    Los 3 elementos a continuación tienen una ejecución en tiempo (coste) constante, O(1)

* Instrucciones simples: la evaluación de expresiones aritméticas siempre que estas sean de tamaño constante así como la comparación de datos simples.
*Las operaciones de asignación, lectura y escritura de datos simples
*Accesos a elementos de un array, a un campo de un registro y a la siguiente posición de un registro de un archivo

    La composición de instrucciones que dependan del tamaño n del problema el coste será igual a la suma de los costes.

    Para las instrucciones de selección en que varios partes del código pueden ser o no ejecutadas según la condición que defina la selección se toma como coste el coste de la peor rama.

    Para los bucles si estos dependen del tamaño del problema se considera orden lineal, pero si están anidados por cada anidación que dependa del tamaño del problema multiplicaremos por n el coste dando lugar a coste cuadráticos, polinómicos o incluso exponenciales

    Para subprogramas resulta de aplicar las anteriores reglas al subprograma, si el número de llamadas al subprograma depende del tamaño del programa (tener en cuenta posibles recursividades) el orden sera mayor dependiendo de como crezca el número de llamadas con el tamaño.

    Si se descompone el coste en partes tenemos que el coste de la unión de cada parte es igual a la que tiene un costo mayor. Es decir si tenemos una parte con un coste lineal y a continuación otra parte con coste cuadrático la unión de las dos nos dará un coste cuadrático (regla de la suma)

    Vamos a continuación a poner dos implementaciones en C de dos algoritmos diferentes para llevar a cabo el mismo problema. Se trata de, a partir de dos números enteros distintos, obtener la suma de todos los números que hay entre ellos incluidos ellos mismos. Por ejemplo si tenemos el 5 y el 10 el algoritmo debe ser capaz de calcular la suma:

5+6+7+8+9+10

#include <stdio.h>

#include <limits.h>



int main(int argc,char** argv)

{

        int min,max;

        unsigned long long i;

        if(argc!=3)

        {

                printf("Error Usage %s minNum maxNum\n",argv[0]);

                return -1;

        }

        min = atoi(argv[1]);

        max = atoi(argv[2]);

        if(min<0 || max<0)

        {

                printf("Max number and min Number must be positive or zero\n");

                return -2;

        }

        if(!(min<max))

        {

                printf("Min number must be less than max number\n");

                return -3;

        }

        if(max>=INT_MAX)

        {

                printf("Sorry, max number must be less than %i\n",INT_MAX);

                return -4;

        }

        for(i=0;min<=max;min++)

        {

                i+=min;

        }

        printf("El resultado es %llu\n",i);

        return 0;

}

#include <stdio.h>

#include <limits.h>



int main(int argc,char** argv)

{

        unsigned long long min,max;

        unsigned long long i;

        if(argc!=3)

        {

                printf("Error Usage %s minNum maxNum\n",argv[0]);

                return -1;

        }

        min = atoi(argv[1]);

        max = atoi(argv[2]);

        if(min<0 || max<0)

        {

                printf("Max number and min Number must be positive or zero\n");

                return -2;

        }

        if(!(min<max))

        {

                printf("Min number must be less than max number\n");

                return -3;

        }

       if(max>=INT_MAX)

        {

                printf("Sorry, max number must be less than %i\n",INT_MAX);

                return -4;

        }

        i=(max+min)*(max+1-min)/2;

        printf("El resultado es %llu\n",i);

        return 0;

}