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 algoritmos

Medir 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 que LENGTH(numbers). Como 1 no es mayor que 6, ejecuta el código dentro del bucle.
Compara numbers[index] con targetNumber. 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 que LENGTH(numbers). Como 2 no es mayor que 6, ejecuta el código dentro del bucle.
Compara numbers[index] con targetNumber. 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 que LENGTH(numbers). Como 3 no es mayor que 6, ejecuta el código dentro del bucle.
Compara numbers[index] con targetNumber. 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.

Comprueba tu comprensión

¿Cuántas operaciones son necesarias para encontrar el número 3, situado en la posición 1 de la lista?

¿Cuantas operaciones se necesitan para encontrar el número 37, localizado en la posición 2 de la lista?

Construyamos una tabla del número de operaciones requeridas de acuerdo con la posición de targetNumber en la lista.

Intenta llenar los espacios en blanco:

Posición en la lista	# de operaciones
1er item en la lista	Tu respuesta debe ser un entero, como $6$ ‍ una fracción propia simplificada, como $3 / 5$ ‍ una fracción impropia simplificada, como $7 / 4$ ‍ un número mixto, como $1 3 / 4$ ‍ un decimal exacto, como $0.75$ ‍ un múltiplo de pi, como $12 pi$ ‍ o $2 / 3 pi$ ‍
2o item en la lista	Tu respuesta debe ser un entero, como $6$ ‍ una fracción propia simplificada, como $3 / 5$ ‍ una fracción impropia simplificada, como $7 / 4$ ‍ un número mixto, como $1 3 / 4$ ‍ un decimal exacto, como $0.75$ ‍ un múltiplo de pi, como $12 pi$ ‍ o $2 / 3 pi$ ‍
3er item en la lista	10
4o item en la lista	Tu respuesta debe ser un entero, como $6$ ‍ una fracción propia simplificada, como $3 / 5$ ‍ una fracción impropia simplificada, como $7 / 4$ ‍ un número mixto, como $1 3 / 4$ ‍ un decimal exacto, como $0.75$ ‍ un múltiplo de pi, como $12 pi$ ‍ o $2 / 3 pi$ ‍
5o item en la lista	Tu respuesta debe ser un entero, como $6$ ‍ una fracción propia simplificada, como $3 / 5$ ‍ una fracción impropia simplificada, como $7 / 4$ ‍ un número mixto, como $1 3 / 4$ ‍ un decimal exacto, como $0.75$ ‍ un múltiplo de pi, como $12 pi$ ‍ o $2 / 3 pi$ ‍
6o item en la lista	Tu respuesta debe ser un entero, como $6$ ‍ una fracción propia simplificada, como $3 / 5$ ‍ una fracción impropia simplificada, como $7 / 4$ ‍ un número mixto, como $1 3 / 4$ ‍ un decimal exacto, como $0.75$ ‍ un múltiplo de pi, como $12 pi$ ‍ o $2 / 3 pi$ ‍

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

n

items. El caso promedio requere

1

operación para inicialización de variables, luego

n / 2

repeticiones del bucle, con

3

operaciones por iteración. Esto es

1 + 3 (n / 2)

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 que maxIndex (6). Como no lo es, ejecuta el código dentro del bucle.
Asigna a middleIndex el promedio de minIndex y maxIndex, redondeado hacia abajo. Eso es FLOOR((1+6)/2), asi que middleIndex ahora almacena 3.
Comprueba si targetNumber es igual a numbers[middleIndex]. Como numbers[3] y targetNumber son ambos 45, el condicional es verdadero y retorna el índice 3.

Guau, este algoritmo de búsqueda binaria encontró el targetNumberen 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 que maxIndex (6). Como no lo es, ejecuta el código dentro del bucle.
Asigna FLOOR((1+6)/2) a middleIndex, así que middleIndex almacena 3.
Comprueba si targetNumber (13) es igual a numbers[middleIndex] (45). No son iguales, así que continúa a la siguiente condición.
Comprueba si targetNumber es mayor que numbers[middleIndex]. No lo es, así que continúa al ELSE.
Asigna a maxIndex el valor middleIndex - 1, así que maxIndex ahora es 2.

Iteración #2:

Comprueba si minIndex (1) es mayor que maxIndex (2). Como no lo es, ejecuta el código dentro del bucle.
Asigna a middleIndex el valor FLOOR((1+2)/2), así que middleIndex almacena 1.
Comprueba si targetNumber (13) es igual a numbers[middleIndex] (3). No son iguales, así que continúa a la siguiente condición.
Comprueba si targetNumber es mayor que numbers[middleIndex]. Como es mayor, asigna a minIndex el valor middleIndex + 1, así que minIndex ahora es 2.

Iteración #3:

Comprueba si minIndex (2) es mayor que maxIndex (2). Como no lo es, ejecuta el código dentro del bucle.
Asigna a middleIndex el valor FLOOR((2+2)/2), así que middleIndex amacena 2.
Comprueba si targetNumber (13) es igual a numbers[middleIndex] (37). No son iguales, así que continúa a la siguiente condición.
Comprueba si targetNumber es mayor que numbers[middleIndex]. No lo es, así que continúa al ELSE.
Asigna a maxIndex el valor middleIndex - 1, así que maxIndex ahora es 1.

Iteración #4:

Comprueba si minIndex (2) es mayor que maxIndex (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.

Comprueba tu comprensión

Tu programa tiene una lista de 10,000 números, ordenada de menor a mayor, y necesitas determinar si el numero está en esa lista.

¿Qué algoritmo usarías?

🙋🏽🙋🏻‍♀️🙋🏿‍♂️¿Tienes alguna pregunta sobre este tópico? Nos encantaría contestarte; ¡simplemente pregunta en el área de preguntas abajo!

[¿Dónde está?]

¿Quieres unirte a la conversación?

Inicia sesión

Ordenar por:

Ivan Camilo Samaca Tovar
Publicado hace hace 10 meses. Enlace directo a la publicación “cómo se hace la operación...” de Ivan Camilo Samaca Tovar
cómo se hace la operación que se necesita para encontrar el numero 37 en la posición 2?
Botón que navega a la página de registroBotón que navega a la página de registro
(1 voto)
Respuesta

¿Sabes inglés? Haz clic aquí para ver más discusiones en el sitio en inglés de Khan Academy.