Ejemplos Big-O

Ejemplos

1

Cuál es el runtime de este código?

void printSumAndProduct(int[] array) {
    int sum = 0;
    int product = 1;
    for (int i = 0; i < array.length; I++) {
        sum += array[i];
    }
    for (int i = 0; i < array.length; i++) {
        product *= array[i];
    } 
    System.out.println(sum + ", " + product);
}

Él runtime seria O(N) - Aunque hayan dos iteraciones sobre el mismo set de datos. Acordamos desacéranos de todas las constantes como N2.

2

Cuál es el runtime de este código?

void printPairs(int[] array) {
    for (int I = 0; i < array.length; i++) {
        for (int j = 0; j < array.length; j++) {
            System.out.println(array[i] + “, “ + array[j]);
        }
    }
}

Él runtime seria O(N * 2). Hay un loop que itera N veces y otro interior que también itera N veces.

3

Y este código que el loop de adentro tiene i + 1?

void printPairs(int[] array) {
    for (int i = 0; i < array.length; i++) {
        for (int j = i + 1; j < array.length; j++) {
            System.out.println(array[i] + ", " + array[j]);
        }
    }
}

Esto nos enseñará algo parecido a:

(1, 2) (1, 3) (1, 4) (1, 5)

(2, 3) (2, 4) (2, 5)

(3, 4) (3, 5)

(4, 5)

Runtime seria O(N*2). Es importante saber que aunque el loop de adentro sea más pequeño que el exterior, no es importante entrar en los detalles ni crear constantes.

4

Y el runtime de este código que tiene dos arrays diferentes?

void printArrays(int[] arrayA, int[] arrayB) {
    for(int a : arrayA) {
        for(int b: arrayB) {
                if(a > b) {
                    System.out.println(a + “, “ + b);
                }
        }
    }
}

Como hemos visto en la pagina anterior - si tuviéramos un loop normal, en este caso arrayA, el runtime seria O(N). Pero ya que tenemos un loop adentro de un loop, el tiempo se multiplicaría ya que los sets de datos son distintos, dandonos un tiempo de O(A * B).

5

Que pasarías sí en el mismo codigo introducimos otro loop interno que tiene un valor constante?

void printArrays(int[] arrayA, int[] arrayB) {
    for(int a : arrayA) {
        for(int b: arrayB) {
            for (int i = 0; i < 1000000; i++) {
                System.out.println(a + ", " + b);       
            }
        }
    }
}

Recordemos siempre que no tomaremos las constantes en consideración. Por lo tanto el tiempo se mantiene como O(A * B).

6

Y este runtime que deja los elementos de un array en reversa? Fíjate que el loop solo hace la mitad del array

static void reverse(int[] array) {
    for (int i = 0; I < array.length / 2; I++) {
        int other = array.length - I - 1;
        int temp = array[I];
        array[I] = array[other];
        array[other] = temp;
    }
}

La respuesta se mantiene igual O(N) - ya que solo hay un set de datos y operaciones con N, ya que el hecho que el loop solo se haga por la mitad crearía una constante que no necesitamos.

7

Cuál de los siguientes ejemplos crees que son igual a O(N)?

// 1.) O(N + P), en donde P = N/2
// 2.) O(2N)
// 3.) O(N + M)

El primero es igual a O(N) ya que P es derivado de N. El segundo sabemos qué es O(N) también por qué tenemos que dejar las constantes. El ultimo se mantiene como es ya que es una suma entre sets de datos distintos.

8

Vamos con un ejemplo mas difícil, Si te diría que tenemos un array con strings - y tenemos que sort cada string del array y después sort el array completo, como lo harías?

String[] strings = {“zxc”, "acd", "ddd", "hola"};

Ya que este problema es más largo intentare romperlo en pedacitos. Aquí hay que entender que contamos con dos variables desde el principio - la 1era siendo la longitud de la string mas larga, la llamaremos S. La segunda siendo el tamaño del array, la llamaremos A.

Sabemos que el tiempo para sort un string es O(S log S),
Sabemos que tenemos que hacer esto por cada string que tenemos - dándonos O(A * S log S)
Ahora tenemos que ordenar todas las strings del array - este es otro pequeño problema dentro del problema. Para comparar un String necesitamos ya un tiempo de O(S), y tenemos que hacer una cantidad de O(A log A) dentro del array. Esto nos deja con un tiempo de O(A * S log A).
Si sumamos ahora ambas partes nos quedaría un tiempo de O(A * S (log A + Log S) ) > No dejes que este ejemplo te desmotive ya que es algo complejo - es bueno solo empezar a tener intuición por el mismo, aunque no se comprenda a profundidad.

9

Qué pasaría si tenemos un Arbol Binario y queremos sumar los valores de todos los nudos?

int sumNodes(Node node) {
    if (node == null) return 0;
    return sumNodes(node.right) + node.value + sumNodes(node.left);
}

Si recordamos la formula de recursividad del capitulo anterior, podríamos ver de que es un algoritmo exponencial por su N, O(Profundidad ^ Ramas). En este caso tenemos dos llamadas recursivas y N seria la cantidad de nudos en la cadena, por lo que quedaría O(2 ^ N). Algunas personas dirían que O(2 ^ Log N) seria mas correcta en este caso - y que se podría simplificar a O(N), pero lo mas comun y aceptable decir O(2 ^ N).

10

Que crees de este algoritmo también recursivo que calcula la función factorial de un numero?

int factorial(int n) {
    if (n < 0) return -1;
    if (n == 0) return1;
    return n * factorial(n - 1);
}

Aquí tenemos una simple llamada recursiva que iría desde n - 1, * n - 2, * n - 3 etc. En este caso esto se simplificaría a O( N ).

11

Miremos un problema un poco mas complejo

void permutation(String string) {
    permutation(string, “”);
}

void permutation(String str, String prefix) {
    if (str.length() == 0) {
        System.out.println(prefix);
    } else {
        for (int i = 0; i < str.length(); i++) {
            String rem = str.substring(0, i) + str.substring(i + 1);
            permutation(rem, prefix + str.charAt(i));
        }
    }
}

Este algoritmo va a imprimir cada posible permutacion de una palabra - Imaginemos que lo hace con ABC.

Una permutación es todos las posibles maneras en las que se puede ordenar un set de datos. En este caso seria como ABC, ACB, BAC, BCA, CAB, CBA. En este tipo de algoritmos occure algo parecido a factorial en donde la función sera llamada N! Cantidad de veces (N siendo la longitud del string). Si N es de length() 4 entonces seria llamada 4 * 3 * 2 * 1.

12

Miremos a una función que computa N Fibonacci

int fib(int n) {
    if (n <= 0) return 0;
    if (n == 1) return 1;
    return fib(n - 1) + fib(n - 2);
}

Generalmente hablando cuando vemos un algoritmo con multiples llamadas repulsivas sabemos de que se trata de O(Ramas ^ Profunidad). En este caso O(2 ^ N),

13

Que pasaría si usamos una tecnica muy famosa llamada Memoization (es una forma de optimizar funciones recursivas mediante guardando resultados pre-computados)

void allFib(int n) {
    int[] memo = new int[n+1];
    for (int I = 0; I < n; I++) {
        System.out.println(I + ", " + fib(I, memo));
    }
}

int fib(int n, int[] memo) {
    if (n <= 0) return 0;
    if (n == 1) return 1;
    if (memo[n] > 0) return memo[n];

    memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
   return memo[n]; 
}

Esto optimizaría cambiaria completamente el algoritmo ya que cambiaria el tiempo desde (2 ^ N) a O(N), una mejora drástica! Esto quiere decir de que en vez de volver a computar todos los valores anteriores para llegar al siguiente numero - el algoritmo solamente los referencia dentro del array de valores pre-computados. Esto lo vuelve un valor constante.

14

Qué piensas de este algoritmo que imprime todos los poderes de 2. 2,4,8,16,32,64.

int powersOf2(int n) {
    if (n <= 0) return 0;
    if (n == 1) return 1;
    int prev = powersOf2(n / 2);
    int cur = prev * 2;
    System.out.println(cur);
    return cur;
}

Si en verdad vemos lo que esta pasando con este algoritmo va partiendo N dentro de 2 cada operación. Por lo que se parece mas a un tipo de función como la de un Binary Tree. Por lo tanto el tiempo seria de O(Log N).