Descargar

Teoría de la complejidad algorítmica

Enviado por rolfpinto

    Teoría de la complejidad algorítmica

    1. Introducción
    2. Complejidad Algorítmica
    3. Tiempo de Ejecución
    4. Asintotas
    5. Órdenes de Complejidad
    6. Reglas de la notación asintótica
    7. Importancia de la Eficiencia
    8. Estimación de la complejidad en algoritmos no recursivos
    9. Bibliografía

    INTRODUCCIÓN

    En la ciencia de la computación los algoritmos son más importantes que los LP o que las computadoras; la solución de un problema haciendo uso de las computadoras requiere por una parte un algoritmo o método de resolución y por otra un programa o codificación del algoritmo en un LP. Ambos componentes tienen importancia; pero la del algoritmo es absolutamente indispensable; sabemos que un algoritmo es una secuencia de pasos para resolver un problema, sus características son:

    2. Independiente: Del LP y de la máquina.

    3. Definido: De pasos claros y concretos.

    4. Finito: En el número de pasos que usará.

    5. Preciso: Cada paso arroja un cálculo correcto.

    6. Recibe datos: Debe poseer datos de entrada.

      Debemos saber que una solución es un conjunto único, pero no es el único conjunto de pasos que entregan la solución, existen muchas alternativas de solución y estas alternativas pueden diferir por:

      • Número de pasos

      • Estructuras

      Ahora que sabemos que existen muchas alternativas de solución para un problema, debemos seleccionar el algoritmo más eficiente, el mejor conjunto de pasos, el que tarde menos en ejecutarse, que tenga menos líneas de código.

      Esta selección puede ser ejecutada a simple vista con sólo observar la cantidad de líneas del programa, pero cuando el programa crece se requiere una medición más exacta y apropiada, para esto se realizan ciertas operaciones matemáticas que establecen la eficiencia teórica del programa, al estudio de estos casos se denomina Complejidad Algorítmica.

      COMPLEJIDAD ALGORÍTMICA

      • Un algoritmo será mas eficiente comparado con otro, siempre que consuma menos recursos, como el tiempo y espacio de memoria necesarios para ejecutarlo.

      • La eficiencia de un algoritmo puede ser cuantificada con las siguientes medidas de complejidad:

      2. Complejidad Temporal o Tiempo de ejecución: Tiempo de cómputo necesario para ejecutar algún programa.
      3. Complejidad Espacial: Memoria que utiliza un programa para su ejecución, La eficiencia en memoria de un algoritmo indica la cantidad de espacio requerido para ejecutar el algoritmo; es decir, el espacio en memoria que ocupan todas las variables propias al algoritmo. Para calcular la memoria estática de un algoritmo se suma la memoria que ocupan las variables declaradas en el algoritmo. Para el caso de la memoria dinámica, el cálculo no es tan simple ya que, este depende de cada ejecución del algoritmo.

      • Este análisis se basa en las Complejidades Temporales, con este fin, para cada problema determinaremos una medida N, que llamaremos tamaño de la entrada o número de datos a procesar por el programa, intentaremos hallar respuestas en función de dicha N.

      • El concepto exacto que cuantifica N dependerá de la naturaleza del problema, si hablamos de un array se puede ver a N como el rango del array, para una matriz, el número de elementos que la componen; para un grafo, podría ser el número de nodos o arcos que lo arman, no se puede establecer una regla para N, pues cada problema acarrea su propia lógica y complejidad.

      Tiempo de Ejecución

      • El tiempo de Ejecución de un programa se mide en función de N, lo que designaremos como T(N).

      • Esta función se puede calcular físicamente ejecutando el programa acompañados de un reloj, o calcularse directamente sobre el código, contando las instrucciones a ser ejecutadas y multiplicando por el tiempo requerido por cada instrucción. Así, un trozo sencillo de código como:

      S1;

      for(x = 0; x < N; x++)

      S2;

      Demanda: T(N) = t1 + t2 * N

      Donde t1 es el tiempo que lleva ejecutar la serie S1 de sentencias, y t2 es el que lleva la serie S2.

      • Habitualmente todos los algoritmos contienen alguna sentencia condicional o selectiva, haciendo que las sentencias ejecutadas dependan de la condición lógica, esto hace que aparezca más de un valor para T(N), es por ello que debemos hablar de un rango de valores:

      Tmin(N) ≤ T(N) ≤ Tmax(N)

      • Estos extremos son llamados "el peor caso" y "el mejor caso" y entre ambos se puede hallar "el caso promedio" o el más frecuente, siendo este el más difícil de estudiar; nos centraremos en el "el peor caso" por ser de fácil cálculo y se acerca a "el caso promedio", brindándonos una medida pesimista pero fiable.

      • Toda función T(N) encierra referencias al parámetro N, y a una serie de constantes Ti dependientes de factores externos al algoritmo. Se tratará de analizar los algoritmos dándoles autonomía frente a estos factores externos, buscando estimaciones generales ampliamente válidas, a pesar de ser demostraciones teóricas.

      Asintotas

      • El análisis de la eficiencia algorítmica nos lleva a estudiar el comportamiento de los algoritmos frente a condiciones extremas. Matemáticamente hablando, cuando N tiende al infinito ¥ , es un comportamiento asintótico.

      • Sean g(n) diferentes funciones que determinan el uso de recursos, pudiendo existir infinidad de funciones g.

      • Estas funciones g serán congregadas en familias, usando como criterio de agrupación su comportamiento asintótico, este comportamiento asintótico es similar cuando los argumentos toman valores muy grandes.

      • Una familia de funciones que comparten un mismo comportamiento asintótico será llamada un Orden de Complejidad. Estas familias se designan con O( ).

      • Para cada uno de estos conjuntos se suele identificar un miembro f(n) que se utiliza como representante de la familia, hablándose del conjunto de funciones g que son del orden de f(n), denotándose como:

      g É O(f(n)), g esta incluido en f(n)

      • Frecuentemente no es necesario conocer el comportamiento exacto, basta conocer una cota superior, es decir, alguna función que se comporte ‘aún peor’.

      • El conjunto O(f(n)) es el de las funciones de orden de f(n), que se define como:

      O(f(n))= { g | $ k Î Â +, $ n0 Î À tales que, n n0, g(n) £ kf(n) }

      O(f(n)) esta formado por aquellas funciones g(n) que crecen a un ritmo menor o igual que el de f(n).

      De las funciones g que forman este conjunto O(f(n)) se dice que están dominadas asintóticamente por f, en el sentido de que para N suficientemente grande, y salvo una constante multiplicativa k, f(n) es una cota superior de g(n).

      Ejemplo: Se puede comprobar que la función g(n) = 3n3 + 2n2, es de O(n3)

      Aplicando la definición dada anteriormente:

      g(n)= 3n3 + 2n2

      f(n)= n3

      n0= 0

      k = 5

      Se tiene: 3n3 + 2n2 £ 5n3, n 0

      n

      g( )

      kf( )

      0

      0

      0

      1

      5

      5

      2

      32

      40

      3

      99

      135

      • El tiempo de ejecución es proporcional, se multiplica por una constante a alguno de los tiempos de ejecución anteriormente propuestos, además de la suma de algunos términos más pequeños. Así, un algoritmo cuyo tiempo de ejecución sea T = 3n2 + 6n se puede considerar proporcional a n2. En este caso se puede asegurar que el algoritmo es del orden de n2, y se escribe O(n2)

      • La notación O( ) ignora los factores constantes, desconoce si se hace una mejor o peor implementación del algoritmo, además de ser independiente de los datos de entrada del algoritmo. Es decir, la utilidad de aplicar esta notación a un algoritmo es encontrar el límite superior de su tiempo de ejecución ‘el peor caso’.

      Órdenes de Complejidad

      • La familia O(f(n)) define un Orden de Complejidad. Elegiremos como representante de este Orden de Complejidad a la función f(n) más sencilla perteneciente a esta familia.

      • Las funciones de complejidad algorítmica más habituales en las cuales el único factor del que dependen es el tamaño de la muestra de entrada n, ordenadas de mayor a menor eficiencia son:

      O(1)

      Orden constante

      O(log n)

      Orden logarítmico

      O(n)

      Orden lineal

      O(n log n)

      Orden cuasi-lineal

      O(n2)

      Orden cuadrático

      O(n3)

      Orden cúbico

      O(na)

      Orden polinómico

      O(2n)

      Orden exponencial

      O(n!)

      Orden factorial

      • Se identifica una Jerarquía de Ordenes de Complejidad que coincide con el orden de la tabla mostrada; jerarquía en el sentido de que cada orden de complejidad inferior tiene a las superiores como subconjuntos.

        • O(1): Complejidad constante. Cuando las instrucciones se ejecutan una vez.

        • O(log n): Complejidad logarítmica. Esta suele aparecer en determinados algoritmos con iteración o recursión no estructural, ejemplo la búsqueda binaria.

        • O(n): Complejidad lineal. Es una complejidad buena y también muy usual. Aparece en la evaluación de bucles simples siempre que la complejidad de las instrucciones interiores sea constante.

        • O(n log n): Complejidad cuasi-lineal. Se encuentra en algoritmos de tipo divide y vencerás como por ejemplo en el método de ordenación quicksort y se considera una buena complejidad. Si n se duplica, el tiempo de ejecución es ligeramente mayor del doble.

        • O(n2): Complejidad cuadrática. Aparece en bucles o ciclos doblemente anidados. Si n se duplica, el tiempo de ejecución aumenta cuatro veces.

        • O(n3): Complejidad cúbica. Suele darse en bucles con triple anidación. Si n se duplica, el tiempo de ejecución se multiplica por ocho. Para un valor grande de n empieza a crecer dramáticamente.

        • O(na): Complejidad polinómica (a > 3). Si a crece, la complejidad del programa es bastante mala.

        • O(2n): Complejidad exponencial. No suelen ser muy útiles en la práctica por el elevadísimo tiempo de ejecución. Se dan en subprogramas recursivos que contengan dos o más llamadas internas. N

      Algoritmos Polinomiales: Aquellos que son proporcionales a na. Son en general factibles o aplicables, los problemas basados en estos algoritmos son solucionables.

      Algoritmos Exponenciales: Aquellos que son proporcionales a kn, k  En general no son factibles salvo un tamaño de entrada n exageradamente pequeño, pero generalmente pertenecen a un universo de problemas de los cuales el cómputo se hace imposible. N

      Reglas de la Notación Asintótica

      1. Si T1(n) y T2(n) son las funciones que expresan los tiempos de ejecución de dos fragmentos de un programa, y se acotan de forma que se tiene:

        T1(n) = O(f1(n)) y T2(n) = O(f2(n))

        Se puede decir que:

        T1(n) + T2(n) = O(max(f1(n), f2(n)))

      2. Regla de la suma
      3. Regla del producto

      Si T1(n) y T2(n) son las funciones que expresan los tiempos de ejecución de dos fragmentos de un programa, y se acotan de forma que se tiene:

      T1(n) = O(f1(n)) y T2(n)=O(f2(n))

      Se puede decir que:

      T1(n) T2(n) = O(f1(n) f2(n))

      IMPORTANCIA DE LA EFICIENCIA

      • ¿Que utilidad tiene diseñar algoritmos eficientes si las computadoras procesan la información cada vez más rápido?

      Bien; para demostrar la importancia de la elaboración de algoritmos eficientes, se plantea el siguiente problema:

      • Contamos con una computadora capaz de procesar datos en 10-4 seg. En esta computadora se ejecuta un algoritmo que lee registros de una base de datos, dicho algoritmo tiene una complejidad exponencial 2n, ¿Cuánto tiempo se tardará en procesar una entrada n de datos?

       

      n

      TIEMPO

      10

      » 1 décima de segundo

      20

      » 2 minutos

      30

      > 1 día

      40

      > 3 años

      50

      = 3 570 años

      100

      = 4,019,693,684,133,150 milenios

      • Ahora se tiene la misma computadora capaz de procesar datos en 10-4 seg. Pero se ejecuta un algoritmo que hace el mismo trabajo antes citado, pero este algoritmo tiene una complejidad cúbica n3, ¿Cuánto tiempo se tardará en procesar una entrada n de datos?

      n

      TIEMPO

      10

      = 1 décima de segundo

      20

      = 8 décimas de segundo

      100

      = 1.7 minutos

      200

      = 13.3 minutos

      1000

      » 1 día

      • Se puede concluir, que solo un algoritmo eficiente, con un orden de complejidad bajo, puede tratar grandes volumen de datos, se razona que un algoritmo es:

      • Muy eficiente si su complejidad es de orden log n

      • Eficiente si su complejidad es de orden na

      • Ineficiente si su complejidad es de orden 2n

      • Se considera que un problema es tratable si existe un algoritmo que lo resuelve con complejidad menor que 2n, y que es intratable o desprovisto de solución en caso contrario.

      ESTIMACIÓN DE LA COMPLEJIDAD EN ALGORITMOS NO RECURSIVOS

      Asignaciones y expresiones simples (=)

      El tiempo de ejecución de toda instrucción de asignación simple, de la evaluación de una expresión formada por términos simples o de toda constante es O(1).

      Secuencias de instrucciones (;)

      El tiempo de ejecución de una secuencia de instrucciones es igual a la suma de sus tiempos de ejecución individuales. Para una secuencia de dos instrucciones S1 y S2 el tiempo de ejecución esta dado por la suma de los tiempos de ejecución de S1 y S2:

      T(S1 ; S2) = T(S1) + T(S2)

      Aplicando la regla de la suma:

      O(T(S1 ; S2)) = max(O( T(S1), T(S2) ))

      Instrucciones condicionales (IF, SWITCH-CASE)

      El tiempo de ejecución para una instrucción condicional IF-THEN es el tiempo necesario para evaluar la condición, más el requerido para el conjunto de instrucciones que se ejecutan cuando se cumple la condición lógica.

      T(IF-THEN) = T(condición) + T(rama THEN)

      Aplicando la regla de la suma:

      O(T(IF-THEN)) = max(O( T(condición), T(rama THEN) ))

      El tiempo de ejecución para una instrucción condicional de tipo IF-THEN-ELSE resulta de evaluar la condición, más el máximo valor del conjunto de instrucciones de las ramas THEN y ELSE.

      T(IF-THEN-ELSE) = T(condición) + max(T(rama THEN), T(rama ELSE))

      Aplicando la regla de la suma, su orden esta dada por la siguiente expresión:

      O(T(IF-THEN-ELSE)) = O( T(condición)) + max(O(T(rama THEN)), O(T(rama ELSE)) )

      Aplicando la regla de la suma:

      O(T(IF-THEN-ELSE)) = max(O( T(condición)), max(O(T(rama THEN)), O(T(rama ELSE)) ))

      El tiempo de ejecución de un condicional múltiple (SWITCH-CASE) es el tiempo necesario para evaluar la condición, más el mayor de los tiempos de las secuencias a ejecutar en cada valor condicional.

      Instrucciones de iteración (FOR, WHILE-DO, DO-WHILE)

      El tiempo de ejecución de un bucle FOR es el producto del número de iteraciones por la complejidad de las instrucciones del cuerpo del mismo bucle.

      Para los ciclos del tipo WHILE-DO y DO-WHILE se sigue la regla anterior, pero se considera la evaluación del número de iteraciones para el peor caso posible. Si existen ciclos anidados, se realiza el análisis de adentro hacia fuera, considerando el tiempo de ejecución de un ciclo interior y la suma del resto de proposiciones como el tiempo de ejecución de una iteración del ciclo exterior.

      Llamadas a procedimientos

      El tiempo de ejecución esta dado por, el tiempo requerido para ejecutar el cuerpo del procedimiento llamado. Si un procedimiento hace llamadas a otros procedimientos "no recursivos", es posible calcular el tiempo de ejecución de cada procedimiento llamado, uno a la vez, partiendo de aquellos que no llaman a ninguno.

      • Ejemplo: función no recursiva que halla el factorial de un número n cualquiera

      int factorial(int n) O(1)

      {

      int fact = 1; O(1)

      for(int i = n; i > 0; i–) O(n)

      fact = fact * i; O(1)

      return fact; O(1)

      }

      Su complejidad es lineal O(n), debido a que se tiene un bucle FOR cuyo número de iteraciones es n.

      • Ejemplo: Si el bucle se repite un número fijo de veces, liberado de n, entonces el bucle introduce una constante que puede ser absorbida.

      int y, z, k = 10; O(1)

      for(int i = 0; i < k; i++) k * O(1)

      {

      y = y + i; O(1)

      z = z + k; O(1)

      }

      Su complejidad es constante; es decir, O(1), debido a que se tiene un bucle for independiente de n.

      • Ejemplo: Dos bucles anidados dependientes de n.

      for(int i = 0; i < n; i++) O(n)

      {

      for(int z = 0; z < n; z++) O(n)

      {

      if(vector[z] > vector[z + 1]) O(1)

      {

      aux = vector[z]; O(1)

      vector[z] = vector[z + 1]; O(1)

      vector[z + 1] = aux; O(1)

      }

      }

      }

      Tenemos O(n) * O(n) * O(1) = O(n2), complejidad cuadrática.

      • Ejemplo: Dos bucles anidados, uno dependiente n y otro dependiente del bucle superior.

      for(int i = 0; i < n; i++) O(n)

      {

      for(int z = n; z < i; z–) O(n)

      {

      if(vector[z] < vector[z – 1]) O(1)

      {

      aux = vector[z]; O(1)

      vector[z] = vector[z – 1]; O(1)

      vector[z – 1] = aux; O(1)

      }

      }

      }

      Tenemos que el bucle exterior se ejecuta n veces Þ O(n), el bucle interno se ejecuta n + … + 3 + 2 + 1 veces respectivamente, o sea (n * (n+1))/2 Þ O(n).

      O(n) * O(n) * O(1) = O(n2), complejidad cuadrática.

      • Ejemplo: Bucles donde la evolución de la variable de control es ascendente no lineal.

      int c = 1; O(1)

      while(c < n) O(log n)

      {

      if(vector[c] < vector[n]) O(1)

      {

      aux = vector[n]; O(1)

      vector[n] = vector[c]; O(1)

      vector[c] = aux; O(1)

      }

      c = c * 2;

      }

      Para este ejemplo al principio el valor de c es 1, al cabo de x iteraciones será 2x Þ el número de iteraciones es tal que n £ 2x donde x es el entero inmediato superior de n; x = log2 n iteraciones, Þ para este caso es:

      O(1) * O(log n) * O(1) = O(log n), complejidad logarítmica.

      • Ejemplo: Bucles donde la evolución de la variable de control es descendente no lineal.

      int c = n; O(1)

      while(c > 1) O(log n)

      {

      vector[c] = c; O(1)

      c = c / 2; O(1)

      }

      Para este ejemplo al principio el valor de c es igual a n, al cabo de x iteraciones será n*2-x Þ el número de iteraciones es tal que n*2-x £ n; un razonamiento análogo nos lleva a log2 n iteraciones, Þ para este caso es:

      O(1) * O(log n) * O(1) = O(log n), complejidad logarítmica.

      • Ejemplo: Bucles donde la evolución de la variable de control no es lineal, junto a bucles con evolución de variable lineal.

      int c, x; O(1)

      for(int i= 0; i < n; i++) O(n)

      {

      c = i; O(1)

      while(c > 0) O(log n)

      {

      x = x % c; O(1)

      c = c / 2; O(1)

      }

      x = x + 2; O(1)

      }

      Tenemos un bucle interno de orden O(log n) que se ejecuta O(log n) veces, luego el conjunto de ordenes es de orden:

      O(1) * O(n) * O(log n) = O(n log n), complejidad cuasi-lineal.

      BIBLIOGRAFIA

      • JOYANES AGUILAR, Luis. Fundamentos de Programación, Algoritmos y Estructuras de datos. España, Seg. Edición McGraw-Hill. 1996

       

       

       

       

      Autor:

      Rolf Manolo Pinto López

      Ingeniero de Sistemas

    7. Arroja información: Debe arrojar información de salida.