LES PRESENTO A LOS DOS ALGORITMOS:
Cuando analizamos el tiempo de ejecución de un algoritmo,se toma en cuenta las estructuras de control (while, for, if-then-else, do). En este caso, en ambos códigos, prestamos atención a la sentencia "while". Las demás sentencias se consideran constantes. ¿Por qué? Por ejemplo las sentencias "int c=N" o "c=c/2" contienen: alocación de memoria y utilización de la ALU para calcular "c/2". Esto se resuelve en tiempo constante.
VOLVIENDO A ALGUNAS CLASES DE MATEMÁTICA ...
Primero definamos el concepto de función matemática.
DEFINICIÓN DE FUNCIÓN [1]
Sean A y B dos conjuntos no vacíos, que llamaremos dominio y codominio respectivamente. Entenderemos por función de A en B toda regla que hace corresponder a cada elemento del dominio un único elemento del codominio. Más precisamente, una función es un conjunto de pares ordenados tales que la primera componente pertenece a A y la segunda componente pertenece a B, es decir, un subconjunto de A X B, de modo que todo elemento de A sea primera componente de un par y sólo de uno. Esto nos dice que toda función de A en B es una relación especial entre A y B.
Se escribe de la siguiente forma:
"f es una función con dominio en A y codominio en B"
En particular,
entonces se tiene
ya que la segunda componente es el cuadrado de la primera.
EL diagrama de Venn correspondiente es
Tanto en la definición de f por extensión como en el diagrama de Venn es fácil advertir que todo elemento del dominio tiene un correspondiente o imagen en el codominio y; además tal correspondiente es único.
Observemos la siguiente situación: elementos distintos de A pueden tener la misma imágen en B. Es decir, f(-1)=1 y f(1)=1.
Ahora bien, pero que tiene que ver esto con el análisis de tiempo de ejecución de los dos algoritmos arriba mencionados?
Debemos de ser capaces de identificar quien es f, A, y B respecto al código arriba mencionado. Es la misma analogía.
SI ANALIZAMOS EL PRIMER CÓDIGO....
Sea N=32, entonces entramos al bloque while cuando c=32, c=16, c=8, c=4, c=2. Pero cuando c=1, ya no entra al while. Entonces nos preguntamos, ¿Cuántas veces entre al bloque while? ¿Cuántas veces se ejecuta el while para N=32? 5 veces. ¿Que tuvimos en cuenta para concluir que se ejecuta 5 veces? Es decir, de que depende que el bloque while se ejecute 5 veces? Depende del valor de "N" y del cálculo "c = c / 2".
Ahora debemos relacionar N con la cantidad de veces que se ejecuta el algoritmo. En este caso, relacionamos N=32 con 5, y esto nos lleva a pensar que
Si 
entonces
entonces
el "while" se va a ejecutar 5 veces.
Si 
entonces
entonces
el "while" se va a ejecutar 6 veces.
Observen que existe un intervalo donde el bloque while se ejecuta la misma cantidad de veces. Esos intervalos son los siguientes:
Podemos concluir que N se ejecuta la misma cantidad de veces para un determinado intervalo, y que dicho intervalo varía en potencias de 2 para el ejemplo del "código 1".
¿Y para que me servía la definición de función?
Sea f:N->M , N y M naturales / f(N)=log2(N)
¿Qué significa N, M y f(N)?
N: Es el valor de entrada que recibe el código. Dependiendo del valor de N, el algorítmo se va a ejecutar más o menos veces.
M: Es el valor aproximado que determina la cantidad de veces que se ejecuta el algoritmo. M depende del valor que tenga N. M no es un número entero cualquiera. M es una unidad de tiempo.
f(N): Es lo que tenemos que descubrir nosotros mismos. Pudimos encontrar que f es de la forma f(N)=log2(N).
Sea f(N)=M=20, siginifica que el algorítmo tarda en ejecutarse 20 unidades de tiempo. ¿Porque la imagen de f son unidades de tiempo y no horas, minutos y segundos? La unidad de tiempo sirve para comparar algoritmos sin depender de la arquitectura subyacente (un algoritmo "tarda" más que otro en ejecutarse). Si uno desea en la práctica estimar el tiempo real, es necesario definir a la unidad de tiempo en horas minutos y segundos.
OBSERVACIÓN: Valores distintos de N pueden tener la misma imagen.
SI ANALIZAMOS EL SEGUNDO CÓDIGO ....
Si N=47, entonces entramos al while cuando c=2, c=4, c=8, c=16, c=32 y cuando c=64 ya no entra al while. Entonces, nos preguntamos, ¿Cuántas veces se ejecuta el while teniendo en cuenta a N y el cálculo c*2? Se ejecuta 5 veces. Ahora debemos relacionar N con la cantidad de veces que se ejecuta el algoritmo. En este caso relacionamos N=45 con 5, y esto nos lleva a pensar que
Tomamos la parte entera de
CONCLUSIÓN
Pudimos analizar que ambos algoritmos tienen el mismo comportamiento asintótico. Es decir, que ambos tardan aproximadamente el mismo tiempo de ejecución para un valor de N dado. Observen que no es de interés obtener un resultado exacto de tiempo de ejecución, ya que es una estimación del mismo.
Bibliografía:
[1] Algebra I, Armando Rojo ( Funciones: Capítulo 4 Página 102 )
