Contenido principal
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
Lección 2: Evaluación de algoritmosMedir la eficiencia de un algoritmo
Un buen algoritmo es correcto, pero un gran algoritmo es correcto y además eficiente. El algoritmo más eficiente es aquel que toma el minimo tiempo de ejecución y uso de memoria posibles, y todavía produce una respuesta correcta.
Contar las operaciones
Una forma de medir la eficiencia de un algoritmo es contar cuántas operaciones necesita para encontrar la respuesta con diferentes tamaños de la entrada.
Comencemos por medir el algoritmo de búsqueda lineal, que encuentra un cierto valor en una lista. El algoritmo examina cada item en la lista, comprobando cada uno para ver si es igual al valor objetivo. Si encuentra el valor, inmediatamente retorna el índice. Si no encuentra el valor después de examinar cada item de la lista, retorna -1.
Así se ve ese algoritmo en pseudocódigo:
PROCEDURE searchList(numbers, targetNumber) {
index ← 1
REPEAT UNTIL (index > LENGTH(numbers)) {
IF (numbers[index] = targetNumber) {
RETURN index
}
index ← index + 1
}
RETURN -1
}
Observa que este pseudocódigo supone que los índices de las listas comienzan en 1.
Sigamos paso a paso este algoritmo para la siguiente entrada de muestra:
searchList([3, 37, 45, 57, 93, 120], 45)
El algoritmo primero inicializa la variable
index
a 1. Luego comienza a iterar.Iteración #1:
- Comprueba si
index
is mayor queLENGTH(numbers)
. Como 1 no es mayor que 6, ejecuta el código dentro del bucle. - Compara
numbers[index]
contargetNumber
. Como 3 no es igual a 45, no ejecuta el código dentro del condicional. - Incrementa
index
en 1, así que ahora almacena 2.
Iteración #2:
- Comprueba si
index
es mayor queLENGTH(numbers)
. Como 2 no es mayor que 6, ejecuta el código dentro del bucle. - Compara
numbers[index]
contargetNumber
. Como 37 no es igual a 45, no ejecuta el código dentro del condicional. - Incrementa
index
en 1, así que ahora almacena 3.
Iteración #3:
- Comprueba si
index
es mayor queLENGTH(numbers)
. Como 3 no es mayor que 6, ejecuta el código dentro del bucle. - Compara
numbers[index]
contargetNumber
. Como 45 sí es igual a 45, ejecuta el código dentro del condicional. - Retorna el valor actual de
index
, 3.
Ahora contemos el número de operaciones que el algoritmo de búsqueda lineal necesitó para encontrar ese valor, es decir la frecuencia que cada tipo de operación se ejecutó.
Operación | # de veces |
---|---|
Inicializa index a 1 | 1 |
Comprueba si index es mayor que LENGTH(numbers) | 3 |
Comprueba si numbers[index] es igual a targetNumber | 3 |
Retorna index | 1 |
Incrementa index en 1 | 2 |
Eso es un total de 10 operaciones para encontrar
targetNumber
en el índice 3. ¿Observas la conexión con el número 3? El bucle se repitió 3 veces, y cada vez ejecutó 3 operaciones. El mejor caso para un algoritmo es la situación que requiere el mínimo número de operaciones. De acuerdo con la tabla, el mejor caso para búsqueda lineal es cuando
targetNumber
es el primer ítem en la lista. ¿Y qué pasa con el peor caso? Según esa tabla, el peor caso es cuando
targetNumber
es el último item en la lista, pues requiere repetir las 3 operaciones del bucle para cada ítem en la lista. En realidad hay un caso ligeramente peor: la situación cuando
targetNumber
no se encuentra en la lista. Esto requerirá un par de operaciones adicionales para comprobar la condición del bucle y retornar -1. Sin embargo, no requiere una repetición adicional del bucle, así que no es mucho peor. Dependiendo de nuestro caso de uso para búsqueda lineal, este peor caso puede ocurrir muy frecuentemente o casi nunca.El caso promedio ocurre cuando
targetNumber
está en la mitad de la lista. Este fue el ejemplo con el que empezamos, que requirió 3 repeticiones del bucle para una lista de 6 ítems.Describamos en terminos más generales la eficiencia para una lista de items. El caso promedio requere operación para inicialización de variables, luego repeticiones del bucle, con operaciones por iteración. Esto es .
La siguiente tabla muestra el número de operaciones para tamaños crecientes de una lista:
Tamaño de la lista | # de operaciones |
---|---|
6 | 10 |
60 | 91 |
600 | 901 |
Veamos eso como una gráfica:
En general, podemos decir que hay una relación "lineal" entre el número de items en una lista y el número de operaciones requeridas por el algoritmo. A medida que crece el número de ítems, el número de operaciones crece proporcionalmente.
Mediciones empíricas
El número de operaciones no nos dice el tiempo que le tomará a una computadora ejecutar un algoritmo. El tiempo de ejecución depende de los detalles de implementación, como la velocidad de la computadora, el lenguaje de programación, y la traducción de dicho lenguaje a código de la máquina. Por esto es que típicamente describimos eficiencia en términos del número de operaciones.
Sin embargo, todavía hay ocasiones en que a un programador le es útil medir el tiempo de ejecución de la implementación de un algoritmo. Tal vez una operación en particular requiere un tiempo sorpresivamente largo, o tal vez hay algún aspecto del lenguaje de programación que frena el algoritmo.
Para medir el tiempo de ejecución, debemos hacer que el algoritmo pueda ejecutarse; tenemos que implementarlo en un lenguaje de programación real.
A continuación, una traducción del pseudocódigo a JavaScript:
function searchList(numbers, targetNumber) {
for (var index = 0; index < numbers.length; index++) {
if (numbers[index] === targetNumber) {
return index;
}
}
return -1;
}
El programa a continuación llama a
searchList()
con una lista de seis números y reporta el tiempo que toma en milisegundos.Si tu computadora es tan rápida como la mía, verás que reporta 0 milisegundos. Esto es porque el algoritmo toma mucho menos tiempo que un milisegundo. Nuestro ambiente de JavaScript no puede medir tiempo en unidades inferiores a milisegundos, sin embargo.
Esto es lo que intentaremos en su lugar: vamos a llamar a
searchList()
100.000 veces, registrar cuántos milisegundos toma esto, y dividir para aproximar el número de nanosegundos por llamada. Eso es lo que hace este programa:En mi computadora, este reporta alrededor de 150 nanosegundos. Hay 1,000,000,000 de nanosegundos en un segundo, así que esto es verdaderamente rápido. En un lenguaje, ambiente o computadora mas veloz, podría ser todavía más rapido..
Eso solo nos indica el tiempo de ejecución promedio de
searchList()
sobre una lista de 6 números. Sin embargo, nos importa más cómo crece el tiempo de ejecución a medida que crece el tamaño de la entrada. ¿Continúa creciendo linealmente, como lo predijo nuestro análisis anterior? El siguiente programa reporta el tiempo de ejecución para listas de 6 números, 60 números y 600 números.
Aquí están los resultados de una ejecución en mi computadora:
Tamaño de la lista | nanosegundos |
---|---|
6 | 50 |
60 | 420 |
600 | 3430 |
Esos puntos están trazados en esta gráfica:
Como se predijo, la relación entre los puntos es más o menos lineal. Al aumentar el número de operaciones por un factor de 10, los nanosegundos aumentan casi en el mismo factor de 10. Los números exactos no son tan limpios como nuestro conteo de operaciones; pero era de esperarse, dado que toda clase de factores del mundo real afectan el tiempo real de ejecución en una computadora.
Mejorar la eficiencia
Múltiples algoritmos pueden resolver correctamente el mismo problema, pero con eficiencias diferentes. Es por eso que la medición de eficiencia algorítmica verdaderamente importa, para ayudarnos a escoger el algoritmo más eficiente.
El algoritmo de búsqueda lineal puede obtener un resultado en tiempo lineal, lo cual es bastante bueno; pero ¿y si hubiese un algoritmo más eficiente? De hecho lo hay, al menos para el caso de una lista ordenada.
El algoritmo de búsqueda binaria puede encontrar eficientemente un valor en una lista ordenada. El algoritmo comienza por comprobar si el valor objetivo es mayor o menor que el valor en la mitad de la lista. Si es mayor, sabe que no puede estar en la mitad inferior de la lista. Si es menor, sabe que no puede estar en la mitad superior de la lista. El algoritmo compara repetidamente el valor objetivo con el valor en la mitad de la lista restante, reduciendo cada vez la lista a la mitad hasta encontrar el valor.
Aqui está cómo se ve eso en pseudocódigo:
PROCEDURE searchList(numbers, targetNumber) {
minIndex ← 1
maxIndex ← LENGTH(numbers)
REPEAT UNTIL (minIndex > maxIndex) {
middleIndex ← FLOOR((minIndex+maxIndex)/2)
IF (targetNumber = numbers[middleIndex]) {
RETURN middleIndex
} ELSE {
IF (targetNumber > numbers[middleIndex]) {
minIndex ← middleIndex + 1
} ELSE {
maxIndex ← middleIndex - 1
}
}
}
RETURN -1
}
Ejecutemos paso a paso este algoritmo. Como el ejemplo de búsqueda lineal usó una lista ordenada, podemos probarlo sobre la misma lista.
searchList([3, 37, 45, 57, 93, 120], 45)
El algoritmo primero inicializa
minIndex
a 1 y maxIndex
a 6.Iteración #1:
- Comprueba si
minIndex
(1) es mayor quemaxIndex
(6). Como no lo es, ejecuta el código dentro del bucle. - Asigna a
middleIndex
el promedio deminIndex
ymaxIndex
, redondeado hacia abajo. Eso esFLOOR((1+6)/2)
, asi quemiddleIndex
ahora almacena 3. - Comprueba si
targetNumber
es igual anumbers[middleIndex]
. Comonumbers[3]
ytargetNumber
son ambos 45, el condicional es verdadero y retorna el índice 3.
Guau, este algoritmo de búsqueda binaria encontró el
targetNumber
en el primer bucle. Solo le tomó 5 operaciones, 2 para el paso de inicialización y 3 operaciones para el bucle. Resulta que este es el mejor caso para este algoritmo: cuando el valor objetivo se encuentra en la mitad de la lista.¿Y qué pasa con el peor de todos los casos, cuando el valor no se encuentra en la lista? Intentemos buscar el número 13 en la misma lista.
El algoritmo primero inicializa
minIndex
a 1 y maxIndex
a 6.Iteración #1:
- Comprueba si
minIndex
(1) es mayor quemaxIndex
(6). Como no lo es, ejecuta el código dentro del bucle. - Asigna
FLOOR((1+6)/2)
amiddleIndex
, así quemiddleIndex
almacena 3. - Comprueba si
targetNumber
(13) es igual anumbers[middleIndex]
(45). No son iguales, así que continúa a la siguiente condición. - Comprueba si
targetNumber
es mayor quenumbers[middleIndex]
. No lo es, así que continúa alELSE
. - Asigna a
maxIndex
el valormiddleIndex - 1
, así quemaxIndex
ahora es 2.
Iteración #2:
- Comprueba si
minIndex
(1) es mayor quemaxIndex
(2). Como no lo es, ejecuta el código dentro del bucle. - Asigna a
middleIndex
el valorFLOOR((1+2)/2)
, así quemiddleIndex
almacena 1. - Comprueba si
targetNumber
(13) es igual anumbers[middleIndex]
(3). No son iguales, así que continúa a la siguiente condición. - Comprueba si
targetNumber
es mayor quenumbers[middleIndex]
. Como es mayor, asigna aminIndex
el valormiddleIndex + 1
, así queminIndex
ahora es 2.
Iteración #3:
- Comprueba si
minIndex
(2) es mayor quemaxIndex
(2). Como no lo es, ejecuta el código dentro del bucle. - Asigna a
middleIndex
el valorFLOOR((2+2)/2)
, así quemiddleIndex
amacena 2. - Comprueba si
targetNumber
(13) es igual anumbers[middleIndex]
(37). No son iguales, así que continúa a la siguiente condición. - Comprueba si
targetNumber
es mayor quenumbers[middleIndex]
. No lo es, así que continúa alELSE
. - Asigna a
maxIndex
el valormiddleIndex - 1
, así quemaxIndex
ahora es 1.
Iteración #4:
- Comprueba si
minIndex
(2) es mayor quemaxIndex
(1). Como sí lo es, no procede más dentro del bucle.
El algoritmo finalmente retorna -1, indicando que el valor no pudo encontrarse.
Ese fue el peor caso para el algoritmo de búsqueda binaria y, sin embargo, solo requirió 3 repeticiones completas del bucle, con alrededor de 4 operaciones por bucle. ¿Recuerdas el peor caso de búsqueda lineal en una lista de 6 números? Tuvo que hacer un bucle para cada número, y requirió 6 repeticiones completas.
Esa es la belleza de la búsqueda binaria: cada iteración reduce el espacio de búsqueda a la mitad, por lo que el algoritmo tiene cada vez menos números que examinar.
Esta tabla ilustra el número de repeticiones del bucle requeridas para varios tamaños de la lista, en el peor de los casos.
Tamaño de la lista | # de repeticiones del bucle |
---|---|
6 | 3 |
60 | 6 |
600 | 10 |
Con búsqueda binaria, ¡una lista de 600 ítems requiere solamente 10 repeticiones del bucle! Con búsqueda lineal, esa misma lista requeriría 600 repeticiones del bucle.
Aqui está la tabla en forma gráfica:
Como puedes ver, la búsqueda binaria es mucho más eficiente que la búsqueda lineal, especialmente si aumenta el tamaño de la lista. Matemáticamente, podemos describir la relación entre el tamaño de la lista y las operaciones para la búsqueda binaria como "logarítmica", que es una tasa de crecimiento mucho más lenta que la relación lineal de la búsqueda lineal.
🙋🏽🙋🏻♀️🙋🏿♂️¿Tienes alguna pregunta sobre este tópico? Nos encantaría contestarte; ¡simplemente pregunta en el área de preguntas abajo!
¿Quieres unirte a la conversación?
- cómo se hace la operación que se necesita para encontrar el numero 37 en la posición 2?(1 voto)