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

ooi-2020/curso-avanzado/sesion-2 at master · omioaxaca/ooi-2020GitHub

VIDEO: https://youtu.be/LbKeqcw6RuY