Análisis temporal

Casos de entrada

Un caso de entrada para un algoritmo es una instancia del problema inicial.

Un algoritmo para resolver un problema de tamaño n, puede recibir una o más entradas, las cuales pueden definir el número de operaciones que hará.
    Se puede determinar que tipos de operaciones utiliza y cuantas veces las ejecuta para una entrada e      específica k
           Por ejemplo realizar una busqueda lineal del 40 en un arreglo de 100,000 elementos                             (n=100,000)

Ejemplo 1. Búsqueda lineal

Operación básica

Del ejemplo notamos que el número de veces que se ejcutan algunas operaciones, para valores sucesivamente mayores que j y/o n; se presenta un modelo de crecimiento similar al que tiene el numero total de operaciones que ejecuta.

Para hacer una estimación de la cantidad de tiempo que tarda un algoritmo en ejecutarse, no es necesario contar el número total de operaciones que realiza

Se puede elegir alguna, a la que se identificará como operación básica que observe un comportamiento parecido al del número total de operaciones realizadas y que, por lo tanto, será proporcional al tiempo total de ejecución.

En general, debe procurarse que la operación básica, en la cual se basa el análisis, de alguna forma esté relacionada con el tio de problema que se intenta resolver, ignorando las asignaciones de valores iniciales y las operaciones sobre variables para control de ciclos (índices)

Ejemplo 2. Producto de 2 mayores

El algoritmo siguiente obtiene el producto de los dos valores más grandes contenidos en un arreglo A de n enteros.

En este algoritmo se realizan las siguientes operaciones:

a) Comparación con los elementos del arreglo

b) Asignaciones a mayor1 y mayor2

c) Asignación al índice i

d) Asignación a la función

e) Producto de los mayores

f) Incremento al índice i

g) Comparación entre el índice i y la longitud del arreglo n

Las operaciones (c), (f) y (g) no se consideran por realizarse entre índices, las operaciones (d) y (e) se ejecutan una sola vez y no son proporcionales al número total de operaciones.

Entones, se tiene que las operaciones que se pueden considerar para hacer el análisis son: (a) Comparación con los elementos del arreglo y (b) las asignaciones a los elementos mayores.

(c), (f), (g),(d) y (e) pueden omitirse para el análisis

(a) y (b) operaciones básicas del algoritmo.

Elección de la operación básica

El análisis d un algoritmo se puede hacer considerando sólo aquella operación que cumpla con los siguientes criterios:

a) Debe estar relacionada con el tipo de problema que se resuelve.

b) Debe ejecutarse un número de veces cuyo modelo de crecimiento sea similar al del número total        de operaciones que efectúa el algoritmo.

Si ninguna de las operaciones encontradas cumple con ambos criterios, es posible declinar por el primero. Si aun así no es posible encontrar una operación representativa, se debe hacer un análisis global, contando todas las operaciones.

Elección de la operación básica para algunos problemas:

• Búsqueda de un elemento en un conjunto
• Comparación ente el valor y los elementos del conjunto
• Multiplicar dos matrices
• Producto de los elementos de las matrices
• Recorrer un árbol
• Visitar un nodo
• Resolver un sistema de ecuaciones lineales
• Suma y resta de las ecuaciones
• Ordenar un conjunto de valores
• Comparación entre valores

Concepto de Instancia

Un problema computacional consiste en una caracterización de un conjunto de datos de entrada, junto con la especificación de la salida deseada con base a cada entrada.

Un problema computacional tiene una o más instancias, que son valores particulares para los datos de entrada, sobre los cuales se puede ejecutar el algoritmo para resolver el problema; i.e. un caso específico de un problema

Ejemplo 

El problema computacional de multiplicar dos números enteros tiene, las siguientes instancias: multiplicar 345 por 4653, multiplicar 2637 por 10000, multiplicar -32341 por 12, etc. 

Análisis Pero Caso, Mejor Caso y Caso Promedio

El comportamiento de un algoritmo puede variar notablemente para diferentes instancias.

Suelen estudiarse tres casos para un mismo algoritmo: caso mejor, caso peor, caso medio.

 Tipos de análisis: 
                • Peor caso: indica el mayor tiempo obtenido, teniendo en consideración todas las entradas                     posibles. 
                • Mejor caso: indica el menor tiempo obtenido, teniendo en consideración todas las                                entradas posibles. 
                • Caso medio: indica el tiempo medio obtenido, considerando todas las entradas posibles. 

Retomando el Ejemplo 1. Búsqueda lineal

Problema. Encontrar la posición de un determinado número en un arreglo desordenado.

¿Cuales serían el peor caso, mejor caso y caso promedio?

*Conclusión: Si se conociera la distribución de los datos, podemos sacar provecho de esto, para un mejor análisis y diseño del algoritmo. Por otra parte, sino conocemos la distribución, entonces lo mejor es considerar el peor de los casos.

Análisis Temporal (mejor, peor y caso medio)

Con los conceptos anteriores es posible llevar a cabo el análisis temporal de un algoritmo i.e. calcular la función complejidad temporal ft(n).

Considérese el Algoritmo del ejemplo 3 (Búsqueda lineal), para hacer el análisis de su comportamiento:

 Operación básica: Comparaciones con elementos del arreglo 

Caso muestra: A = [2, 7, 4, 1, 3] y n = 5: 

             • Si Valor = 2, se hace una comparación, ft (5) = 1 

             • Si Valor = 4, se hacen tres comparaciones, ft (5) = 3 

             • Si Valor = 8, se hacen cinco comparaciones, y ft (5) = 5 

Del análisis anterior es posible descubrir que la función complejidad temporal no es tal, en realidad es una relación, ya que para un mismo tamaño de problema se obtienen distintos valores de la función complejidad.

 Para la mayoría de los algoritmos el número de operaciones depende, no sólo del tamaño del problema, sino también de la instancia específica que se presente (caso de entrada).

Sea:

I(n)={I1 , I2 , I3 , …, Ik } el conjunto de instancias del problema de tamaño n. 

O(n)={O1 , O2 , O3 , …, Ok } el conjunto formado por el número de operaciones que un algoritmo realiza para resolver cada instancia.

Entonces, Oj es el número de operaciones ejecutadas para resolver la instancia Ij , para 1 ≤ j ≤ k.

Se distinguen tres casos en el valor de la función complejidad temporal

El mejor caso se presenta cuando para un caso de entrada I1 a un problema de tamaño n; el algoritmo ejecuta el mínimo número posible de operaciones.

El peor caso se presenta cuando para un caso de entrada I2 a un problema de tamaño n; el algoritmo ejecuta el máximo número de operaciones.

El caso medio se consideran todos los casos posibles para calcular el promedio de las operaciones que se hacen tomando en cuenta la probabilidad de que ocurra cada instancia I3 .

Retomando el Ejemplo 1. Búsqueda lineal

Algoritmo: Búsqueda lineal

Problema: Búsqueda lineal de un valor en un arreglo de tamaño n: 

Tamaño del Problema: n = número de elementos en el arreglo.  

Operación básica: Comparación del valor con los elementos del arreglo A[i]!=Valor.

Análisis Temporal

Mejor caso: ocurre cuando el valor es el primer elemento del arreglo. 

                          f t (n)= 1 (Una comparación A[i]!=Valor)

Peor caso: sucede cuando el valor es el ultimo en el arreglo o no se encuentra en el arreglo.

                          f t (n)=n (n comparaciones A[i]!=Valor)

Caso medio: 

                          f t (n)=1P(1) + 2P(2) + 3P(3) + 4P(4) +... + nP(n) + nP(n + 1) 

Donde P(i) es la probabilidad de que el valor se encuentre en la localidad i; (1 ≤ i ≤ n) y P(n + 1) es la probabilidad de que no esté en el arreglo y el número que lo acompaña es la cantidad de operaciones básicas para cada uno de ellos

Si se supone que todos los casos son igualmente probables

Retomando el Ejemplo 2. Productos Mayores

Algoritmo: Producto mayores. 

Problema: Dado un arreglo de valores, encontrar el producto de los dos números mayores. 

Tamaño del Problema: n =número de elementos en el arreglo. 

Operación básica: Comparasión con los elementos del arreglo y las asignaciones a los elementos mayores. 

Análisis Temporal

Mejor caso: ocurre cuando el arreglo está ordenado descendentemente (se realiza la primer comparación y dos asignaciones, posteriormente solo se compara n-2 veces el if y n-2 veces el else if). 

Peor caso: el arreglo está ordenado de manera ascendente (se realiza la primer comparación y dos asignaciones, posteriormente solo se compara n-2 veces el if y siempre se cumplirá por lo que hará 2(n-2) asignaciones.

Caso medio: en este problema se tienen (|𝑈  |/𝑛) 𝑛! casos, donde U es el conjunto del que se extraen los elementos del arreglo. 

(|𝑈  |/𝑛)Determina el número de posibles conjuntos de n elementos del conjunto U

𝑛! Determina el número de maneras de acomodar los n elementos

Para hacer el cálculo se deben de contar las operaciones que se harían en cada caso. (Laborioso y complicado)

El algoritmo hace siempre una comparación al inicio y dos asignaciones y en el interior del ciclo puede ser que se realice una comparación con dos asignaciones, dos comparaciones con una asignación o dos comparaciones y ninguna asignación; obsérvese que para cada A[i] puede ser cierta una de tres aseveraciones: 

         • A[i] > mayor1: Se hace una comparación y dos asignaciones 

         • A[i]≤mayor1 && A[i]>mayor2: Se hacen dos comparaciones y una asignación 

         • A[i]≤mayor1 && A[i]≤mayor2 : Se hacen dos comparaciones 

Caso medio. Si cada caso tien la misma probabilidad de ocurrencia en promedio se harán:

Es importante mencionar que no todos los algoritmos presentan casos que hacen variar la complejidad temporal para un tamaño de problema especifico, y resulta interesante tener una herramienta de análisis para detectar cuándo se particionará el análisis en casos; por el momento la única ayuda con la que se cuenta es la intuición y preguntarse: ¿Se puede resolver el problema de manera trivial para alguna instancia específica?. Si la respuesta es afirmativa el algoritmo tendrá casos, por lo que el problema de detección se reduce a contestar esta “simple” pregunta.