En el post previo Big-O en español Parte 1, revisamos la notación de Big-O para expresiones lineales y constantes, en este post vamos a revisar las expresiones cuadráticas y exponenciales.

Expresiones cuadráticas

Como en el ejemplo anterior, vamos a utilizar ejemplos para explicar esta notación

Supongamos que tenemos un arreglo, de todas las selecciones de futbol masculino que salieron campeonas del mundo desde el año 1930, en el arreglo solo usamos el nombre del país, sin considerar, en cada mundial que ganaron.

const campeonesMundiales = ["Uruguay", "Italia", "Italia","Uruguay","Alemania",
                            "Brasil", "Brasil","Inglaterra", "Brasil","Alemania", "Argentina",
                            "Italia", "Argentina", "Alemania","Brasil","Francia",
                            "Italia", "España", "Alemania","Francia"]

Supongamos ahora que tenemos todas las selecciones que van a disputar el mundial de Qatar.

const seleccionesQatar = ["Qatar", "Alemania", "Dinamarca","Brasil","Francia",
                            "Paises Bajos", "Argentina","Iran", "Corea del Sur","Japon", "Arabia Saudita",
                            "Ecuador", "Uruguay", "Canada","Ghana","Senegal","Marruecos", "Tunez","Portugal",
                            "Polonia", "Camerun", "Mexico","Estados Unidos", "Gales","Australia","Costa Rica"]

Ahora supongamos que queremos saber cuáles de las selecciones que van a disputar Catar, salieron campeonas y cuentas veces.

El siguiente ejemplo muestra un código de como

  function ListarCampeones(){
   
    for (let i = 0; i < seleccionesQatar.length; i++) {
        const seleccion = seleccionesQatar[i];
        let count=0;
        for (let j = 0; j < campeonesMundiales.length; j++) {
            const campeon = campeonesMundiales[j];
            if (seleccion === campeon)
                count++
        }
        console.log(`La selección ${seleccion} - ${ (count=== 0 ? " no ha salido Campeona del mundo": "Ganó  " + count + "Mudiale/s"  )  } `)
        count =0;
    }
}

Como se puede ver en el ejemplo, estamos verificado por cada selección que va a disputar Qatar, cual está en la lista de campeonas del mundo y estamos contando cuantas veces lo fueron, o indicando que no salieron campeonas mundiales.

En este ejemplo tenemos dos bucles (for) anidados, lo cual en base a la explicación que de la Parte 1, cada vez cada bucle tiene una complejidad línea f(x)=x, con lo cual si juntamos las complejidades no daría

f(x)=x*x = x^2

Cuanto más grande sean los arreglos, más tiempo va a demorar en procesar todas las combinaciones.

Expresiones cubicas y elevadas a la cualquier potencia

Si seguimos agregando más bucles (for) al algoritmo, vamos a seguir multiplicando expresiones lineales f(x)=x, con lo cual… si agregamos tres bucles será f(x)=x * x * x = x ^3 , si tenemos 4 bucles anidados será f(x) = x * x * x *x = x ^4 y así sucesivamente

A continuación, se puede ver la grafica de cantidad de elementos en función del tiempo

Exponential

La grafica muestra que cuanto más elevada es la potencia, mayor tiempo lleva en procesar los elementos.

En lo posible, siempre hay que optimizar la utilización de estos bucles y optimizar como leer los arreglos.

En el próximo Post vamos a hablar de otros tipos de Expresiones (Logarítmicas, Exponenciales y Factoriales).