Medir la eficiencia de un algoritmo

Una tienda en línea maneja un inventario de millones de productos. En su página principal, muestra a sus clientes productos relacionados con los que han comprado recientemente.

El siguiente procedimiento encuentra una lista de productos similares para una lista de productos dada:

PROCEDURE findSimilarProducts(products) {
   similarProducts ← [] 
   FOR EACH product IN products {
     similarProduct ← calcSimilar(product)
     APPEND(similarProducts, similarProduct)
   }
   RETURN similarProducts
}

El procedimiento calcSimilar() toma 2 minutos en regresar un resultado, ya que necesita hacer una serie complicada de búsquedas de bases de datos y de operaciones matemáticas. Las otras operaciones, crear la lista vacía y añadir elementos a la lista, solo toman algunos nanosegundos.

Si la tienda invoca el procedimiento con una lista de 5 productos, ¿cuánto tiempo tardará aproximadamente en ejecutar?

🤔

Este código está escrito en pseudocódigo. No puedes ejecutar pseudocódigo, pero lo usamos para planificar programas y pensar en código independientemente de un lenguaje de programación específico.

Las preguntas del examen AP CSP usan pseudocódigo, por lo que es útil familiarizarse con él.

Aquí hay una referencia para el pseudocódigo usado aquí:

PROCEDURE nombre (parámetro1, parámetro2, . .)
{
     <instrucciones>
     RETURN (expresión)
}

Un procedimiento llamado "nombre" que toma cero o más parámetros. El procedimiento contiene instrucciones de programación y retorna el valor de expresión.

a ← expresión

Evalúa expresión y asigna el resultado a la variable a.

lista ← [valor1, valor2, valor3]

Crea una lista con 3 valores. El primer valor se encuentra en el índice 1, el segundo en el índice 2, el tercero en el índice 3.

APPEND(lista, item)

Añade item al final de lista, incrementando la longitud de la lista en 1.

FOR EACH valor IN lista
{
   <instrucciones>
}

Asigna secuencialmente a valor el valor de cada elemento de lista, comenzando por el primer elemento y terminando con el último. Ejecuta el código en instrucciones una vez para cada valor.

Contenido relacionado

Artículo

Medir la eficiencia de un algoritmo

Principios de ciencias de la computación avanzados (AP Computer Science Principles)

Curso: Principios de ciencias de la computación avanzados (AP Computer Science Principles) > Unidad 4

Problema