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 algoritmosCategorizar eficiencia de tiempo de ejecución
Es importante entender la eficiencia de ejecución de los algoritmos que usamos. Cuando una computadora toma demasiado tiempo para resolver un problema, cuesta más dinero y te priva del tiempo que podrías usar en otros problemas valiosos. Además, si el algoritmo se usa en una aplicación que interactúa con el usuario, puede resultar en que usuarios frustrados abandonen el uso de la aplicación por completo.
Categorización de tiempos de ejecución
Podemos categorizar el tiempo de ejecución de un algoritmo de acuerdo a cómo aumenta el número de pasos conforme crece el tamaño de su entrada. ¿Toma siempre el mismo tiempo? Esto es un aumento constante, un tiempo de ejecución muy rápido. ¿Requiere siempre examinar todas las posibles permutaciones de la entrada? Esto es un aumento exponencial, un tiempo de ejecución muy lento. La mayoría de los tiempos de ejecución están entre estos dos extremos.
Tiempo constante
Cuando un algoritmo corre en tiempo constante, quiere decir que siempre toma un numero fijo de pasos, sin importar qué tanto crece el tamaño de la entrada.
Como un ejemplo, considera acceder el primer elemento de una lista.
firstPost ← posts[1]Aun si la lista crece a tener un millón de ítems, esta operación siempre requerirá un solo paso.
Podemos visualizar esta relación como una tabla:
| Tamaño de la lista | Pasos |
|---|---|
| 1 | 1 |
| 10 | 1 |
| 100 | 1 |
| 1000 | 1 |
También podemos visualizarla como un gráfico.
Un tiempo constante es ideal, pero típicamente no es posible para algoritmos que procesan múltiples pedazos de datos.
Tiempo logarítmico
Cuando un algoritmo corre en tiempo logarítmico, su tiempo de ejecución aumenta proporcionalmente al logaritmo del tamaño de la entrada.
El algoritmo de búsqueda binaria es un algoritmo que corre en tiempo logarítmico. Lee el articulo sobre medida de eficiencia para una explicación más a fondo del algoritmo.
Aquí está el 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
}El algoritmo usa un bucle para examinar múltiples ítems en la lista, pero crucialmente, no examina todos los ítems de la lista. Específicamente, examina log, start base, 2, end base, n ítems, donde n es el número de ítems de la lista.
Podemos visualizar esa relación en una tabla:
| Tamaño de la lista | Pasos |
|---|---|
| 1 | 1 |
| 10 | 4 |
| 100 | 7 |
| 1000 | 10 |
También podemos visualizarla como un gráfico.
El número de pasos definitivamente crece al crecer el tamaño de la entrada, pero a una tasa muy lenta.
Tiempo lineal
Cuando un algoritmo corre en tiempo lineal, su número de pasos crece en proporción directa al tamaño de la entrada
El apropiadamente llamado algoritmo de búsqueda lineal corre en tiempo lineal.
El pseudocódigo muestra su simplicidad comparada con búsqueda binaria.
PROCEDURE searchList(numbers, targetNumber) {
index ← 1
REPEAT UNTIL (index > LENGTH(numbers)) {
IF (numbers[index] = targetNumber) {
RETURN index
}
index ← index + 1
}
RETURN -1
}Esta vez, el bucle examina cada ítem de la lista. Esta búsqueda exhaustiva es necesaria para buscar items en una lista no ordenada, puesto que no hay manera de enfocarse donde un ítem particular pueda estar ubicado. Este algoritmo siempre requiere al menos tantos pasos como ítems tenga la lista.
Podemos ver esto en forma tabular:
| Tamaño de la lista | Pasos |
|---|---|
| 1 | 1 |
| 10 | 10 |
| 100 | 100 |
| 1000 | 1000 |
O como un gráfico:
Tiempo cuadrático
Cuando un algoritmo crece en tiempo cuadrático, sus pasos aumentan proporcionalmente al cuadrado del tamaño de la entrada.
Varios algoritmos para ordenamiento de listas corren en tiempo cuadrático, como ordenamiento por selección. Ese algoritmo comienza desde la cabeza de la lista, continúa buscando el siguiente valor más pequeño en la lista y lo intercambia con el valor actual.
Aquí está el pseudocódigo para ordenamiento por selección.
i ← 1
REPEAT UNTIL (i > LENGTH(numbers)) {
minIndex ← i
j ← i + 1
// Encuentra el siguiente valor más pequeño
REPEAT UNTIL (j > LENGTH(numbers)) {
IF (numbers[j] < numbers[minIndex]) {
minIndex ← j
}
}
// Intercambia si se encuentra nuevo mínimo
IF (minIndex != i) {
tempNum ← numbers[minIndex]
numbers[i] ← tempNum
numbers[minIndex] <- tempNum
}
}Lo importante a observar en el algoritmo es el bucle anidado: enumera los ítems de la lista, y para cada uno de esos items, ejecuta el bucle otra vez sobre los ítems restantes. En este caso, el algoritmo examina start fraction, 1, divided by, 2, end fraction, left parenthesis, n, squared, minus, n, right parenthesis valores, donde n es el número de ítems en la lista.
Esta tabla muestra cuántos ítems examinaría para listas cada vez más grandes.
| Tamaño de lista | Pasos |
|---|---|
| 1 | 1 |
| 10 | 45 |
| 100 | 4950 |
| 1000 | 499,500 |
Aqui está como eso se vería en forma de gráfico:
Tanto la tabla como el gráfico muestran que el número de pasos para este algoritmo aumenta a una velocidad mucho más rápida que los anteriores.
Tiempo exponencial
Cuando un algoritmo crece en tiempo superpolinomial, su número de pasos aumenta más rápido que una función polinomial del tamaño de la entrada.
Un algoritmo frecuentemente requiere tiempo superpolinomial cuando tiene que examinar toda permutación posible de valores. Por ejemplo, considera un algoritmo que genera todas las posibles contraseñas numéricas para una longitud de contraseña dada.
Para una longitud de contraseña de 2, genera 100 contraseñas.
0 1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29
30 31 32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47 48 49
50 51 52 53 54 55 56 57 58 59
60 61 62 63 64 65 66 67 68 69
70 71 72 73 74 75 76 77 78 79
80 81 82 83 84 85 86 87 88 89
90 91 92 93 94 95 96 97 98 99 Ese algoritmo requiere al menos 10, squared pasos, dado que hay 10 posibilidades para cada dígito (0-9) y tiene que ensayar todas las posibilidades para cada uno de los 2 dígitos.
Dada una longitud n de contraseña, el algoritmo requiere 10, start superscript, n, end superscript pasos. Este tiempo de ejecución crece increíblemente rápido, pues cada digito adicional requiere 10 veces más número de pasos.
Esta tabla muestra que tan rápido crece esto para solo los primeros 5 dígitos:
| Digitos | Pasos |
|---|---|
| 1 | 10 |
| 2 | 100 |
| 3 | 1000 |
| 4 | 10,000 |
| 5 | 100,000 |
Aquí está cómo se ve eso en un gráfico:
Ahora todo junto
Ahora que ya vimos ejemplos de tiempos de ejecución posibles de algoritmos, comparémosolos en un gráfico:
Este gráfico deja aún más claro que existe una diferencia definitiva entre estos tiempos de ejecución, especialmente a medida que crece el tamaño de la entrada. Como los programas de computadoras modernas manejan conjuntos de datos cada vez más grandes (como de millones de usuarios o sensores), la eficiencia del tiempo de ejecución importa mucho.
Polinomial versus superpolinomial
En ciencias de la computación a menudo se clasifican los tiempos de ejecución en dos clases:
- Tiempo polinomial describe cualquier tiempo de ejecución que no crece mas rápido que n, start superscript, k, end superscript, lo que incluye tiempo constante (n, start superscript, 0, end superscript), tiempo logarítmico (log, start base, 2, end base, n), tiempo lineal (n, start superscript, 1, end superscript), tiempo cuadrático (n, squared), y otros polinomios de orden superior (como n, cubed).
- Tiempo superpolinomial describe cualquier tiempo de ejecución que crece más rápido que n, start superscript, k, end superscript, e incluye tiempo exponencial (2, start superscript, n, end superscript), tiempo factorial (n, !), y cualquiera más rápido.
¿Por qué distinguimos entre polinomial y superpolinomial?
Esta tabla de tiempos de ejecución ilustra por qué:
| 10 | 50 | 100 | 300 | 1000 | |
|---|---|---|---|---|---|
| 5, n | 50 | 250 | 500 | 1500 | 5000 |
| n, squared | 100 | 2500 | 10000 | 90000 | |
| n, cubed | 1000 | 125000 | |||
| 2, start superscript, n, end superscript | 1024 | ||||
| n, ! |
Estos números no tienen unidades, asi que un algoritmo n, ! puede correr en 3.6 million de nanosegundos si n es 10, lo cual es menos de un segundo. Si n es 50, correría en 3, times, 10, start superscript, 64, end superscript nanosegundos; ¡pero han pasado solamente 10, start superscript, 26, end superscript nanosegundos desde el Big Bang! Un tiempo superpolinomial con frecuencia requiere más tiempo que el disponible en el universo, aun para tamaños relativamente pequeños de la entrada.
Es por esto que pensamos que los tiempos de ejecución polinomiales son razonables y que los tiempos superpolinomiales no son razonables. Un tiempo de ejecución polinomial no siempre es ideal (y frecuentemente tratamos de mejorar estos tiempos), pero al menos es factible.
Los científicos de computación concentran sus esfuerzos en encontrar algoritmos de tiempo polinomial para aquellos problemas que en la actualidad requieren tiempo superpolinomial, dado que es ahi donde la diferencia importa más.
Más aprendizaje
El "Análisis asintótico" es un método mas formal de analizar la eficiencia algorítmica. Esto no esta cubierto aqui, pero si estás interesado, puedes aprender más sobre análisis asintótico en nuestro curso de algoritmos a nivel universitario.
🙋🏽🙋🏻♀️🙋🏿♂️¿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?
Hola, espero estén bien. Quería saber si era posible que se probara el pseudocódigo de ordenamiento por selección ejemplicado en esta explicación, debido a que intentándolo probar asignando una lista de números no le encuentro la lógica a su implementación, es decir, no hallo que efectivamente se esté dando solución al problema.
Quien pueda ayudarme le estaré muy agradecida.(1 voto)