Big O notation y estructura de datos.

A quien no le ha tocado una entrevista en la cual le pregunten Big O notation?, o simplemente le ha tocado resolver un problema en alguno de los programas como hackerrank, leetcode, etc., y no ha podido resolverlo debido a la falta de práctica o simplemente porque saliendo de la universidad dejo de practicar esa área que no se utiliza en el día a día en un trabajo.

En mi experiencia, eh perdido muchas buenas posiciones por no tener ese skill tan bien desarrollado como otros devs.

Pero me eh tomado un poco el tiempo para poder explicarlo lo mejor posible y que a futuros desarrolladores no les tomen por sorpresa cómo me ah pasado a mí!.

Primero que nada , revisemos la definición y lo que compone Big O notation.!

¿Que es Big O Notation?

La notación Big O es una forma de describir el rendimiento de un algoritmo, cómo crece el número de operaciones necesarias para completarlo a medida que crece el tamaño de la entrada. En cualquier lenguaje de programacion, esto se puede utilizar para analizar el rendimiento de varias operaciones, como ordenar un arreglo o buscar en un diccionario.

Big O también se le conoce como el límite superior del algoritmo, ya que analiza la peor situación.

El mejor de los casos generalmente no nos dice nada: es posible que resolvamos el problema en el primer intento. Es por eso que empleamos los peores escenarios para obtener información significativa. Nos dice que algoritmo siempre funcionará igual o mejor que el peor de los casos.

Ahora, el algoritmo y la estructura de datos que eliges mientras se programa el código es crítico. La notación Big O hace que sea más fácil comparar el rendimiento de diferentes algoritmos y averiguar cuál es el mejor para tu código.

Para la informática, Big O Notation es una función matemática utilizada para determinar la dificultad de un algoritmo. Define el tiempo que se tarda en ejecutar un algoritmo. También te ayudará a determinar cómo cambiará el rendimiento de tu algoritmo a medida que crezca el tamaño de entrada.

¿Cómo se mide la eficiencia de un algoritmo?

La eficiencia se mide de dos maneras: la complejidad del tiempo y la complejidad del espacio.

La complejidad del tiempo

La complejidad temporal (time complexity) es una medida del rendimiento de un algoritmo en función del tamaño de la entrada. Se expresa comúnmente utilizando la notación de “Big O”, que indica el límite superior de la tasa de crecimiento del tiempo de ejecución del algoritmo.

Por ejemplo, si un algoritmo tiene una complejidad temporal de O(n), significa que el tiempo de ejecución aumenta proporcionalmente al tamaño de la entrada (n).

La complejidad espacial

La complejidad espacial (space complexity) es una medida del uso de memoria por un algoritmo en función del tamaño de la entrada. Al igual que la complejidad temporal, se expresa utilizando la notación de “Big O”.

Por ejemplo, si un algoritmo tiene una complejidad espacial de O(n), significa que el uso de memoria aumenta proporcionalmente al tamaño de la entrada (n).

Es importante tener en cuenta que la complejidad temporal y espacial son solo una aproximación y no siempre reflejan el rendimiento real de un algoritmo. Sin embargo, son útiles para comparar diferentes algoritmos y elegir el más adecuado para un problema específico.

La gente suele confundir el espacio auxiliar con la complejidad del espacio. El espacio auxiliar no es el equivalente a la complejidad del espacio, pero es parte de ella. El espacio auxiliar es solo el espacio temporal o adicional, mientras que la complejidad del espacio también incluye el espacio utilizado por los valores de entrada.

En pocas palabras:

Complejidad espacial = Espacio auxiliar + Espacio utilizado por los valores de entrada.

Los mejores algoritmos/programas deberían tener la menor complejidad del espacio. Cuanto menor sea el espacio utilizado, más rápido se ejecutará.

Idealmente, las complejidades del espacio y el tiempo dependen de varios factores, como el hardware, el sistema operativo, CPU, el procesador, etc. Pero para mantener las cosas simples, normalmente no tenemos en cuenta estos factores al analizar el rendimiento de un algoritmo.

Las siguientes son las principales complejidades del tiempo y el espacio:

• Constante: O(1)
• Tiempo lineal: O(n)
• Tiempo logarítmico: O(n log n)
• Tiempo cuadrático: O(n²)
• Tiempo exponencial: 2 ^(n)
• Tiempo factorial: O(n!)

Pero, ¿por qué necesitamos Big O?

En el mundo en el que vivimos hoy en día consiste de aplicaciones y software complicados, cada uno de los cuales se ejecuta en varios dispositivos y cada uno con diferentes capacidades. Algunos dispositivos, como los ordenadores de sobremesa (o Desktop en ingles), pueden ejecutar software de aprendizaje automático pesado, pero otros, como los teléfonos, solo pueden ejecutar aplicaciones. Por lo tanto, cuando creas una aplicación, tendrás que optimizar tu código para que funcione sin problemas en todos los dispositivos y darte una ventaja sobre tus competidores.

Como resultado, los programadores deben inspeccionar y evaluar su código a fondo. Esta hoja de trucos para Big O Notation (una hoja de trucos de complejidad temporal en todas las estructuras de datos) te ayudará a entender una serie de complicaciones.

Una explicación simple de esta grafica con ejemplos seria la siguiente:

Siguiendo la grafica nuestro primer ejemplo seria:

O(n²)

Un ejemplo seria ordenar un arreglo, el ordenamiento burbuja tiene una notación Big O de O(n²) porque en el peor de los casos tendrás que comparar cada elemento n veces y hacer n-1 intercambios.

Si en algun momento una función contiene 3 bucles anidados, probablemente sea O(n³) o tiempo cúbico. Cuatro bucles anidados serían O(n⁴) y así sucesivamente.En caso de duda, solo añade el número de bucles anidados y deberías estar en un buen camino.

En el siguiente ejemplo, el ordenamiento burbuja tiene una notación Big O de O(n²) porque en el peor de los casos tendrá que comparar cada elemento n veces y hacer n-1 intercambios.

NSMutableArray *numbers = [@[@4, @2, @1, @3, @5] mutableCopy];
for (int i = 0; i < numbers.count; i++) {
    for (int j = 0; j < numbers.count - i - 1; j++) {
        if ([numbers[j] intValue] > [numbers[j + 1] intValue]) {
            [numbers exchangeObjectAtIndex:j withObjectAtIndex:j+1];
        }
    }
}

O(n)

Una búsqueda lineal simple a través de un arreglo de n elementos tendría una notación Big O de O(n), ya que el número de operaciones requeridas para encontrar un elemento específico en el arreglo es directamente proporcional al tamaño del arreglo.

En el siguiente ejemplo, la búsqueda lineal tiene una notación Big O de O(n), ya que el número de operaciones necesarias para encontrar un elemento específico en el arreglo es directamente proporcional al tamaño del arreglo.

//Objective-C

NSArray *numbers = @[@1, @2, @3, @4, @5];
int searchValue = 3;
BOOL found = NO;
for (int i = 0; i < numbers.count; i++) {
    if ([numbers[i] intValue] == searchValue) {
        found = YES;
        break;
    }
}
// Swift 
let numbers = [1, 2, 3, 4, 5]
let searchValue = 3
var found = false
for number in numbers {
    if number == searchValue {
        found = true
        break
    }
}

O(log n)

Quicksort tiene una notación Big O de O(n log n) debido a que utiliza un enfoque de dividir y conquistar para ordenar el arreglo.

Una búsqueda binaria a través de un arreglo ordenado de n elementos tendría una notación Big O de O(log n), ya que el número de operaciones requeridas para encontrar un elemento específico en el arreglo es logarítmico con respecto al tamaño del arreglo.

En el siguiente ejemplo, la búsqueda binaria tiene una notación Big O de O(log n), ya que el número de operaciones requeridas para encontrar un elemento específico en el arreglo es logarítmico con respecto al tamaño del arreglo.

//Objective-C
NSArray *numbers = @[@1, @2, @3, @4, @5];
int searchValue = 3;
int low = 0;
int high = (int)numbers.count - 1;
while (low <= high) {
    int mid = (low + high) / 2;
    if ([numbers[mid] intValue] < searchValue) {
        low = mid + 1;
    } else if ([numbers[mid] intValue] > searchValue) {
        high = mid - 1;
    } else {
        NSLog(@"Encontrado en el indice: %d", mid);
        break;
    }
}

// Swift 
let numbers = [1, 2, 3, 4, 5]
let searchValue = 3
var low = 0
var high = numbers.count - 1
while low <= high {
    let mid = (low + high) / 2
    if numbers[mid] < searchValue {
        low = mid + 1
    } else if numbers[mid] > searchValue {
        high = mid - 1
    } else {
        print("Encontrado en el indice: \(mid)")
        break
    }
}

O(1)

Cuando no hay dependencia del tamaño de entrada n, se dice que un algoritmo tiene un tiempo de orden constante O(1):

Un ejemplo claro de nuestro tiempo constante seria imprimir nuestro primer elemento de un arreglo, sin importar el tamaño del arreglo siempre se tratara de imprimir el primer valor.

//Objective-C
NSArray *numbers = @[@1, @2, @3, @4, @5];
NSLog(@"%@",numbers[0]);

// Swift 
let numbers = [1, 2, 3, 4, 5]
print("primer elemento\(numbers[0])")

Después de esta breve explicación, existe un par de pasos los cuales nos ayudan a ver si nuestra respuesta es optima o se puede mejorar.!

Paso #1: Cuenta los pasos

Supongamos teóricamente que tenemos un código muy típico y malo, en el cual tenemos una función la cual recibe un arreglo e imprime un elemento del arreglo, en este caso imprimirá el primer valor, pero que pasaria si en vez de imprimir el primer valor en un arreglo de 5, fuera un arreglo de 10,000?

-(void)print_first_item(NSArray* items_Array)
{
   NSLog(@"%@",items_Array[0]);
}

Para nuestro propósito, seria el mismo porque imprimirá el primer valor del arreglo sin importar cuantos números fueran en el arreglo, ah este pequeño código podemos decir que su tiempo de ejecucion es O(1).

Ahora, digamos que tenemos una función que pasó por un bucle. Esto significa que pase lo que pase, tenemos la garantía de pasar por cada elemento del ciclo al menos una vez, dependiendo de lo que la función intente lograr. Si tenemos un solo ciclo, como en el código a continuación, lo llamaríamos O(n), o “tiempo lineal”, porque el tiempo de ejecución aumentará linealmente a medida que aumente la entrada. Esto significa que si tenemos 5 elementos en una matriz, imprimiríamos los 5 elementos. Si la entrada de la matriz fuera 1000, la imprimiríamos 1000 veces.

-(void)singleLoop(NSArray* items_Array)
{
for (int i = 0; i < items_Array.count; i++) 
  {
    NSLog(@"valor del arreglo en el indice %d: valor %@", i, items_Array[i]);
  }
}

// Ejemplo con for in loop 

-(void)singleLoop(NSArray* items_Array)
{
   for (id obj in myArray) 
     {
      NSLog(@" valor de matriz: %@", obj);
     }
}

¿Ves cómo el tiempo aumenta a un ritmo constante y predecible a medida que crece la entrada de datos? ¡Eso es lo que significa lineal, una línea recta! Si pensamos en nuestro O(1) anterior, o tiempo constante, por ejemplo, vemos que el tiempo de ejecución se mantiene, bueno, constante sin importar cuánto crezca nuestra entrada de datos, n .

Paso #2: Se añaden diferentes pasos

Ok, como vimos antes ,una introducción rápida a los bucles, pero ¿qué pasa con los algoritmos que tienen más de una cosa en marcha? ¡Gran pregunta! Una cosa importante para recordar sobre Big O es que n tiene que significar algo. Si estás tratando con más de un algo, entonces necesitará más de una variable. Además, n es solo una variable de práctica común, pero podemos describir fácilmente todas las funciones que hemos visto hasta ahora como algo más, como O(4), O(a), O(b²), O(🧐), etc.

Así que echamos un vistazo a la siguiente función.

-(void)agregandoTiemposDeEjecución(NSArray* items_A,)
           con:(NSArray * items_B)
{
    for(id item in items_A) 
  {
    NSLog(@"elementos del primer arreglo: %@",item);       // O(a)
  }


    for(id elementos in items_B)
   {
     NSLog(@"elementos del segundo arreglo: %@",elemento);  // O(b)
   } 

}

Similar a nuestros ejemplos anteriores, estamos tratando con dos bucles en una función. Esta función, sin embargo, no tiene los bucles anidados. En cambio, recorremos items_A, imprimimos los resultados, luego pasamos a items_B y hacemos lo mismo. En este ejemplo, necesitamos dos variables para describir lo que sucede porque estamos tomando el tiempo de ejecución para cada entrada. Aquí, las dos entradas son independientes entre sí y no se componen, por lo que nuestra complejidad temporal sería O(a + b).

La tentación de multiplicar las dos entradas, u O(a*b), es fuerte, pero debemos recordar que Big O se trata de cómo se escala el algoritmo a medida que aumentan las entradas. En el escenario anterior, items_A no se ve afectado si items_B crece, por lo que debemos tratarlos como dos variables distintas. Gayle Laakmann McDowell, autora de “Cracking the Coding Interview”, lo expresó mejor:

Si su algoritmo tiene la forma ‘haga esto, luego, cuando haya terminado, haga eso’, entonces agrega los tiempos de ejecución. Si su algoritmo tiene la forma ‘haga esto cada vez que haga eso’, entonces multiplica los tiempos de ejecución”.

Paso #3: Constantes y coeficientes de caída

Cada paso del algoritmo tiene una complejidad constante, por lo que no hay constantes ni coeficientes que tengamos que preocuparnos.

¡Si, lo haz leído bien! Cuando se trata de Big O, no nos importan las constantes o los coeficientes porque lo que realmente buscamos es cómo se escala la función.

-(void)compareItemsInArrays(NSArray* items_A,)
           with:(NSArray * items_B)
{
    for(id item in items_A) 
  {
    NSLog(@"elementos del primer arreglo: %@",item);      // O(a)
   if ([item isEqual:@10]) {
        NSLog(@"Item is equal to 10.");
    }
 
  }

    for(id elementos in items_B)
   {
     NSLog(@"elementos del segundo arreglo: %@",elemento);  // O(b)
        if ([item isEqual:@10]) {
        NSLog(@"Item is equal to 10.");
    }
   } 
 
}

Tomando el ejemplo anterior, se puede describir como O(2n+2), con 2n proveniente de dos bucles que ejecutan la matriz única y 2 de la última línea de cada for in loop en el cual cada if imprime si encuentra el numero 10 en cada interacción y solo imprime un mensaje que el item es igual a 10. Aunque podríamos estar tentados a decir definitivamente que es O( 2n +2) y nada más, estaríamos equivocados. Nuevamente, nos importa la escala de este algoritmo, por lo que primero debemos eliminar las constantes y los coeficientes.

¿Qué es una constante?

En este caso, es 2 en O(2n+2). Tiene sentido eliminarlo porque 2 nunca cambiará incluso si nuestra entrada del arreglo aumentara en un 1000%.
Así que ahora nos quedamos con O(2n). En este caso, 2 es nuestro coeficiente, lo que significa que es un valor numérico por el que estamos multiplicando nuestra variable. Una vez más, estamos interesados en la escala de nuestro algoritmo, por lo que decir O(2n) frente a O(n + 2) frente a O(n) no cambia el hecho de que siempre tendrá un tiempo de ejecución lineal.

Al final del día, ni las constantes ni los coeficientes juegan un papel importante a medida que nuestra entrada de datos, n (o sea la letra que decidiste utilizar), se acerca al infinito.

Paso #4: Dejar caer términos no dominantes.

Digamos que tenemos un algoritmo que hemos calculado como O(2n³ + 5n³)

-(void)complexFunction:(NSInteger)n 
{
    int result = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                result++;
            }
        }
    }
    for (int l = 0; l < 5*n; l++) {
        for (int m = 0; m < n; m++) {
            for (int o = 0; o < n; o++) {
                result++;
            }
        }
    }
    NSLog(@"Resultado: %d", result);
}

Explicando la función anterior tiene una complejidad temporal de O(2n³ + 5n³) porque tiene 2 bucles anidados de 3 bucles anidados cada uno, con n iteraciones en cada bucle más interno. El primer bloque de bucles se ejecuta n³ veces y el segundo bloque de bucles se ejecuta 5*n³ veces, lo que equivale a 5n³. Por lo tanto, la complejidad del tiempo total es O(2n³ + 5n³) = O(n³) de manera resumida.

Wow, vemos un código realmente de miedo!, pero ¿cómo podemos reducir esto? Primero, debemos deshacernos del coeficiente 5 por las razones discutidas anteriormente. Ahora nos queda O(n³ + n³). Recuerde que Big O tiene que ver con la escala, por lo que queremos eliminar el término no dominante, también conocido como la(s) parte(s) de la expresión que juegan un papel menos significativo a medida que aumenta nuestra entrada. En este caso, nuestro término no dominante sería n³, dejándonos con O(n³) como nuestro tiempo de ejecución.

Paso #5: Diferentes entradas obtienen diferentes variables.

Finalmente, cuando se trata de múltiples entradas, debemos recordar usar múltiples variables. Después de todo, n en O(n) es una entrada de datos, no solo una letra aleatoria que alguien decidió colocar entre paréntesis. Si tenemos múltiples entradas de datos, cada una debe tener su propia variable única para reconocer su relación.

-(void)differentInputs(NSArray* items_A,)
           with:(NSArray * items_B)
{
   int count = 0;
   for(id item in items_A) 
  {
   for(id elementos in items_B)
   {
   
        if (item == elementos) 
      {
        count += 1;
      }
   }
 
  }


}

En la función anterior, tenemos dos matrices, items_A y items_B. Aquí estamos diciendo “por cada elemento en items_A, revisa todos los elementos en items_B. Por lo tanto, el tiempo de ejecución de esta función se puede describir como O(a*b) porque la longitud de cada ciclo se multiplica por la longitud del otro.

Para facilitar nuestro trabajo ya existe una tablita con el rendimiento de los algoritmos mas comunes utilizados en los lenguajes de programacion, te la presento a continuacion:

En Resumen.

La notación Big O es una pregunta de muchas empresas estadounidenses y toman mucho en cuenta si tienes el conocimiento de cómo medirlo, muchas veces a la empresa no le interesa si sabes como usar el lenguaje de programación o si tienes un conocimiento previo, pero para resumir que es la notación Big O es una forma de medir el rendimiento de un algoritmo en términos del crecimiento del tamaño de la entrada.

En Objective-C y en cualquier lenguaje de programación, se utiliza para analizar el rendimiento de los métodos y las funciones de un programa. Un algoritmo con una complejidad temporal de O(1), por ejemplo, es constante y no cambia su tiempo de ejecución independientemente del tamaño de la entrada. Por otro lado, un algoritmo con una complejidad temporal de O(n²) aumenta su tiempo de ejecución de forma cuadrática con el tamaño de la entrada. Es importante tener en cuenta que la notación Big O no tiene en cuenta los factores constantes y solo se enfoca en el crecimiento a medida que aumenta el tamaño de la entrada.

¡Gracias por leer! Si tiene algún comentario o sugerencia sobre cómo mejorar este artículo, no dude en comentarlo. ¡Gracias!

Recursos.

Un buen recurso para introducirte a fondo de Big O es este video con Raywenderlich que explica al igual que en este post lo que es la grafica de notacion y sus diferencias.https://www.youtube.com/watch?v=6jYSlk1SOeY&list=PL23Revp-82LJQgdlhnwwVPF5cceOS5uCu&index=1.

Otro buen recurso es este video con la ingeniera Gayle Laakmann McDowell en el cual explica Big O junto con sus 5 pasos de una manera muy sencilla https://www.youtube.com/watch?v=v4cd1O4zkGw.