Sesión 2

Clase del 20 de febrero de 2020.

Temas

Complejidad de un algoritmo y conceptos de uso de memoria.

Complejidad de un algoritmo

Notación O: La complejidad del algoritmo en el peor de los casos.

Necesitamos entender lo siguiente:

  • ¿Cuántas operaciones realiza nuestro algoritmo?

  • ¿En cuanto tiempo se traducen esas operaciones?

IMPORTANTE: Una computadora "promedio" puede realizar 10^6 (1,000,000) operaciones en 1 segundo.

  • Complejidad constante O(1)

int x = 5;

x = 5 + 8;

x = 5 * 1000;

  • Complejidad lineal O(n)

    for(int i = 0; i < n; i++) {
   x = 5 + 8;
}

  • Complejidad cuadratica O(n^2)

for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
        x = 5 + 8;
    }
}

  • Complejidad exponencial O(x^n)

    • Pendiente

  • Complejidad factorial O(n!)

    • Pendiente

Códigos

VIDEO: https://youtu.be/LbKeqcw6RuY

PreviousSesión 1NextSesión 3-4

Last updated