Análisis de Algoritmos - Algoritmos y Programación II

Como ya mencionamos antes, podemos entender a un algoritmo como un método para resolver un problema dado en una computadora. Un algoritmo describe los pasos que se deben seguir para alcanzar el resultado buscado.

Para un problema cualquiera, puede existir más de un algoritmo que lo resuelva. Un algoritmo puede consumir más o menos recursos que otro que resuelve el mismo problema, por lo tanto una de las principales variables de análisis generalmente es la eficiencia en el uso de los recursos.

Otro aspecto a tener en cuenta al analizar algoritmos es la simplicidad. Un algoritmo simple es más fácil de entender, adaptar y mantener, por eso a veces prima la simplicidad a la hora de elegir un algoritmo.

La simplicidad y la eficiencia no son conceptos antagónicos. Es decir, un algoritmo puede ser simple y eficiente a la vez. Estas métricas sirven principalmente para comparar algoritmos entre sí y así poder elegir el más adecuado para una situación concreta.

1Complejidad¶

En esta definición de complejidad entra en juego una variable más, la cantidad o el tamaño de los datos, por ejemplo si tenemos que ordenar pocos datos, y rara vez se agregan nuevos datos o se modifican los existentes, quizás prime la simplicidad del algoritmo a la hora de elegir alguno de los algoritmos de ordenamiento, pero si tenemos que ordenar millones de datos, donde además se agregan cientos o miles de datos y se modifican otros muy frecuentemente, es probable que nos interese analizar cuánto tiempo va a demorar y cuánta memoria o espacio en disco vamos a necesitar y más aún, cuánto más necesitaremos a medida que aumente el volumen de datos, es decir, es probable que prime la eficiencia a la hora de elegir.

Informalmente hablando, cuanto mayor sea la complejidad de un algoritmo, será menos eficiente en el uso de los recursos.

La complejidad es independiente del hardware o la máquina donde se ejecuta el algoritmo. No debemos confundir complejidad con rendimiento.

El rendimiento sí depende del hardware. Por ejemplo en la medida que aumenta la velocidad del procesador, se necesitará menos tiempo para completar una tarea dada. En cambio la complejidad nos indica cuanto más tiempo o memoria va a requerir el algoritmo en función del tamaño de los datos.

En esta primera aproximación al estudio del análisis de algoritmos, nos vamos a enfocar en la complejidad temporal. Como la complejidad temporal es una métrica independiente del hardware donde se ejecuta el programa, normalmente se estima contando la cantidad de operaciones elementales que realiza el algoritmo bajo análisis para completar el cálculo, teniendo en cuenta que cada unidad elemental requiere una cantidad fija de tiempo, que por simplicidad se asume como una unidad de tiempo.

Como la cantidad de operaciones elementales que debe realizar depende de los datos, se toma siempre el peor caso, para poder obtener una cota confiable. Por ejemplo si hay que buscar un elemento en un arreglo desordenado, no queda otra que buscar el elemento en todas las posiciones del arreglo. En el peor caso se deberá recorrer todo el arreglo para encontrar el elemento en la última posición escrutada o poder concluir que el elemento no se encuentra, es probable que si ejecutamos nuestro algoritmo muchas veces, algunas veces lo encuentre antes de recorrer todo el arreglo, pero como buscamos una cota, se toma siempre el peor caso.

2Cota Superior Asintótica (O grande)¶

La cota superior asintótica, O grande o Big-O en inglés, es parte de la familia de notaciones asintóticas, también conocidas como notaciones de Bachmann-Landau. En ciencias de la computación, la O grande, permite clasificar a los algoritmos de acuerdo a como aumenta la cantidad de recursos que necesita en la medida que aumenta el tamaño de la entrada, es decir nos permite clasificar algoritmos en el límite, cuando el tamaño de la entrada tiende a infinito. Sea $T(n)$ la función que indica cuánto tiempo va a tardar un algoritmo en función del tamaño de la entrada $n$ , donde $n$ es un número natural, entonces:

Esto quiere decir que la tasa de crecimiento de $T(n)$ es menor o igual a la tasa de crecimiento de $f(n)$ . Es decir la tasa de crecimiento de $T(n)$ está acotada por arriba por $f(n), \; \forall n > n_0$ .

Por ejemplo, si tenemos la función $T(n) = 4 n + 1$ , se verifica que es de la familia de $O(n)$ , es decir la tasa de crecimiento de $T(n)$ está acotada por $f(n) = n$ , ya que:

\exists \; c = 5, \; n_0 = 1

(2)

tal que:

5 n \ge 4 n + 1, \; \forall n \ge 1

(3)

Función Acotada: T(n) \subset O(n) — Función Acotada: $T(n) \subset O(n)$

A continuación se muestran algunas tasas de crecimiento de las funciones que comúnmente se encuentran al calcular la O grande.

En la siguiente tabla se muestran algunas de las funciones más comunes y sus nombres

Orden	Nombre
$O(1)$	constante
$O(log_2(n))$	logarítmica
$O(n)$	lineal
$O(n \; log_2(n))$	casi lineal
$O(n^2)$	cuadrática
$O(k^n)$	exponencial

2.1Propiedades de la O grande¶

Propiedad transitiva

Si,

T(n) = O(f(n)) \quad \land \quad f(n) = O(g(n))

(4)

entonces:

T(n) = O(g(n))

(5)

Multiplicación por una constante

Si,

T(n) = O(f(n)) \quad \land \quad k \ne 0

(6)

entonces:

O(k \, T(n)) = k \cdot O(T(n)) = O(f(n))

(7)

Propiedad de la suma

Si,

T_1(n) = O(f(n)) \quad \land \quad T_2(n) = O(g(n))

(8)

entonces:

T_1(n) + T_2(n) = \max(O(f(n)), O(g(n)))

(9)

Propiedad del producto

Si,

T_1(n) = O(f(n)) \quad \land \quad T_2(n) = O(g(n))

(10)

entonces:

T_1(n) \cdot T_2(n) = O(f(n) \cdot g(n))

(11)

Propiedad de los polinomios

Si,

T(n) = c_k \, n^k + c_{k-1} \, n^{k-1} + \dots + c_1 \, n + c_0

(12)

es decir $T(n)$ es un polinomio de grado $k$ , entonces:

T(n) = O(n^k)

(13)

3Cálculo de la O grande¶

Como ya se mencionó, para poder calcular el orden de un algoritmo se necesita contar cuantas operaciones elementales realiza.

3.1Operaciones elementales (OE)¶

Las operaciones elementales son lo que tienen un costo de 1 es decir cuyo tiempo de ejecución es 1 (una unidad genérica de tiempo).

Las siguientes son OE:

Asignación o consulta de una variable simple.
Operaciones aritméticas elementales de valores simples (suma, resta, multiplicación, división y resto).
Comparaciones (mayor, mayor igual, igual, distinto, menor y menor igual).
Operaciones lógicas (and, or y not).
Acceso indexado a un elemento simple de un arreglo.
Desreferenciar un puntero.

3.2Operaciones complejas¶

Por operaciones complejas entendemos a los condicionales, los ciclos y la ejecución de funciones. Estas operaciones en general pueden anidar otras operaciones.

Condicionales

\texttt{if} \; \langle C \rangle \; \texttt{then} \; \langle S_1 \rangle \; \texttt{else} \; \langle S_2 \rangle

(14)

entonces:

T(n) = T(C) + \max(T(S_1), T(S_2))

(15)

Ciclos

\texttt{for} \; \langle C \rangle \; \{ \; \langle S \rangle \; \}

(16)

entonces:

T(n) = T(C) + \langle iteraciones \rangle \cdot (T(C) + T(S))

(17)

Ejecución de Funciones

F(P_1, P_2, P_3, \dots, P_n) \; \{ \; \langle S \rangle \; \}

(18)

entonces:

T(n) = 1 + T(P_1) + T(P_2) + T(P_3) + \dots +T(P_n) + T(S)

(19)

3.3Ejemplos de cálculo¶

3.3.1Búsqueda Lineal¶

En este ejemplo vamos a implementar el algoritmo de búsqueda lineal para buscar un elemento dentro de un arreglo. El algoritmo se puede enunciar como:

A continuación una implementación en Go:

1
2
3
4
5
6
7
8
func busquedaLineal(arreglo []int, objetivo int) int {
    for i := 0; i < len(arreglo); i++ {
        if arreglo[i] == objetivo {
            return i
        }
    }
    return -1
}

Para calcular el tiempo de ejecución de un algoritmo, conviene empezar por las operaciones elementales que se encuentran más anidadas. En este ejemplo la línea 4 dentro del condicional es $O(1)$ .

Evaluar la condición arreglo[i] == objetivo (línea 3) también es $O(1)$ ya que se trata de accesos a valores y una comparación, por lo tanto:

T(\langle condicional \rangle) = O(1)

(20)

Entonces dentro del ciclo for tenemos un condicional de $O(1)$ y la actualización del índice (i++) que también es una operación simple y por lo tanto es $O(1)$ . Podemos concluir que todo el cuerpo del ciclo es $O(1)$ .

T(\langle ciclo \rangle) = O(1) + n \, O(1) = O(n)

(21)

ya que evaluar la condición del ciclo, i < len(arreglo), también es $O(1)$ (donde $n$ es la longitud del arreglo).

La línea 7 también es $O(1)$ .

T(n) = O(1) + O(n) + O(1) = O(n)

(22)

3.3.2Búsqueda Binaria¶

Implementación en Go:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func busquedaBinaria(lista []int, elemento int) int {
    L := 0
    R := len(lista) - 1
    for L <= R {
        M := (L + R) / 2
        if lista[M] < elemento {
            L = M + 1
            continue
        }
        if lista[M] > elemento {
            R = M - 1
            continue
        }
        return M // Se encontró el elemento
    }
    return -1 // No se encontró
}

Para analizar la búsqueda binaria, la primera observación que podemos realizar es que los condicionales son $O(1)$ . Siguiendo el mismo razonamiento, todas las instrucciones que se realizan fuera del ciclo for también son OE. Por lo tanto podemos plantear la siguiente ecuación de recurrencia:

T(n) = T \left( \frac{n}{2} \right) + c

(23)

Donde $T(\frac{n}{2})$ representa que en cada vuelta del ciclo mientras se descarta la mitad del arreglo. La constante $c$ representa todas las operaciones $O(1)$ que se realizan en cada vuelta del ciclo. Para resolverla podemos suponer que n es una potencia de 2. Es decir:

n = 2^k

(24)

Reemplazando obtenemos:

Primera vuelta del ciclo

T(n) = T \left( \frac{2^k}{2} \right) + c = T(2^{k-1}) + c

(25)

Segunda vuelta del ciclo

T(n) = T(2^{k-2}) + 2 \, c

(26)

\dots

(27)

Vuelta $i$ del ciclo

T(n) = T(2^{k-i}) + i \, c

(28)

entonces para $i = k$

Vuelta $k$ del ciclo

T(n) = T(1) + k \, c

(29)

$T(1)$ es cuanto cuesta si el arreglo tiene tamaño 1, es decir L == R, y por lo tanto solo ejecuta una iteración del bucle para determinar si el elemento es el buscado o ajustar los índices para salir. Entonces $T(1) = O(1)$

podemos despejar $k$ de la ecuación $n = 2^k$ y nos queda que $k = log_2(n)$ . Finalmente queda:

T(n) = O(1) + c \; log_2(n)

(30)

T(n) = O(log_2(n))

(31)

Es decir al tener el arreglo ordenado, la búsqueda binaria necesita realizar mucho menos operaciones que la búsqueda lineal para encontrar el valor buscado o determinar que no existe. La clave está en descartar la mitad del arreglo en cada vuelta del ciclo for.

4Ejercicios¶

Máximo entre dos números. Dado el siguiente pseudocódigo, calculá la cantidad de operaciones elementales que ejecuta y determiná su O grande:
```
1
2
3
4
5
6
7
FUNCION maximo(x, y)
    SI x >= y ENTONCES
        RETORNAR x
    SINO
        RETORNAR y
    FIN SI
FIN FUNCION
```
Algoritmo máximo

Potencia. Dado el siguiente pseudocódigo, calculá la cantidad de operaciones elementales y determiná su O grande:

1
2
3
4
5
6
7
FUNCION potencia(x, n)
    resultado ← 1.0
    PARA i ← 0 HASTA n-1 HACER
        resultado ← resultado * x
    FIN PARA
    RETORNAR resultado
FIN FUNCION

Algoritmo potencia

Recorrer un arreglo. Dado el siguiente pseudocódigo, calculá la cantidad de operaciones elementales y determiná su O grande:

1
2
3
4
5
6
7
8
FUNCION listarAlumnos(a)
    i ← 0
    MIENTRAS i < LONGITUD(a) HACER
        ESCRIBIR a[i].nombre + " " + a[i].apellido
        i ← i + 1
    FIN MIENTRAS
    RETORNAR
FIN FUNCION

Algoritmo listar alumnos

Fragmentos de código. Para cada uno de los siguientes fragmentos, determiná el tiempo de ejecución en notación O grande:

1
2
3
PARA i ← 0 HASTA n-1 HACER
    sum ← sum + 1
FIN PARA

Fragmento 1

1
2
3
PARA i ← 0 HASTA n-1 PASO 2 HACER
    sum ← sum + 1
FIN PARA

Fragmento 2

1
2
3
4
5
PARA i ← 0 HASTA n-1 HACER
    PARA j ← 0 HASTA n-1 HACER
        sum ← sum + 1
    FIN PARA
FIN PARA

Fragmento 3

1
2
3
4
5
6
PARA i ← 0 HASTA n-1 HACER
    sum ← sum + 1
FIN PARA
PARA j ← 0 HASTA n-1 HACER
    sum ← sum + 1
FIN PARA

Fragmento 4

1
2
3
4
5
PARA i ← 0 HASTA n-1 HACER
    PARA j ← 0 HASTA n*n-1 HACER
        sum ← sum + 1
    FIN PARA
FIN PARA

Fragmento 5

1
2
3
4
5
PARA i ← 0 HASTA n-1 HACER
    PARA j ← 0 HASTA i-1 HACER
        sum ← sum + 1
    FIN PARA
FIN PARA

Fragmento 6

1
2
3
4
5
6
7
PARA i ← 0 HASTA n-1 HACER
    PARA j ← 0 HASTA n*n-1 HACER
        PARA k ← 0 HASTA j-1 HACER
            sum ← sum + 1
        FIN PARA
    FIN PARA
FIN PARA

Fragmento 7