Esta página se tradujo automáticamente con la API de traducción de Google Cloud.
Algunas páginas se pueden leer mejor en su totalidad.
En informática, el análisis asintótico es el proceso de determinar la complejidad computacional de los algoritmos a medida que aumenta el tamaño de entrada. Se utiliza para describir el rendimiento de un algoritmo en términos de la cantidad de tiempo o espacio requerido para ejecutarlo.
Hay tres formas comunes de representar la complejidad asintótica de un algoritmo:
En esta publicación, veremos cada una de estas notaciones y cómo se pueden usar para describir la complejidad asintótica de los algoritmos.
La notación Big-O se utiliza para describir el peor de los casos de un algoritmo. Da un límite superior a la complejidad asintótica de un algoritmo.
Por ejemplo, considere el siguiente algoritmo para encontrar el elemento máximo en una matriz:
function findMax(arr) {
let max = arr[0];
for (let i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
El peor de los casos para este algoritmo es cuando el elemento máximo está al final de la matriz. En este caso, el algoritmo tomará n
pasos, donde n
es el tamaño de la matriz. Por lo tanto, la complejidad asintótica de este algoritmo es O(n).
La notación Big-O se usa a menudo para describir la complejidad asintótica de los algoritmos en términos del tamaño de entrada. Por ejemplo, la complejidad asintótica del algoritmo findMax anterior es O(n), donde n es el tamaño de la matriz de entrada.
La notación Big-Θ se utiliza para describir la complejidad asintótica de un algoritmo en el mejor y el peor de los casos. Da un límite estrecho a la complejidad asintótica de un algoritmo.
Por ejemplo, considere el siguiente algoritmo para encontrar el elemento máximo en una matriz:
function findMax(arr) {
let max = arr[0];
for (let i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
El peor de los casos para este algoritmo es cuando el elemento máximo está al final de la matriz. En este caso, el algoritmo tomará n
pasos, donde n
es el tamaño de la matriz. El mejor de los casos es cuando el elemento máximo está al principio de la matriz. En este caso, el algoritmo tomará 1 paso. Por tanto, la complejidad asintótica de este algoritmo es Θ(n).
La notación Big-Θ se usa a menudo para describir la complejidad asintótica de los algoritmos en términos del tamaño de entrada. Por ejemplo, la complejidad asintótica del algoritmo findMax anterior es Θ(n), donde n es el tamaño de la matriz de entrada.
La notación Big-Ω se utiliza para describir el mejor de los casos de un algoritmo. Da un límite inferior a la complejidad asintótica de un algoritmo.
Por ejemplo, considere el siguiente algoritmo para encontrar el elemento máximo en una matriz:
function findMax(arr) {
let max = arr[0];
for (let i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
El mejor de los casos para este algoritmo es cuando el elemento máximo está al comienzo de la matriz. En este caso, el algoritmo tomará 1 paso. Por lo tanto, la complejidad asintótica de este algoritmo es Ω(1).
La notación Big-Ω se usa a menudo para describir la complejidad asintótica de los algoritmos en términos del tamaño de entrada. Por ejemplo, la complejidad asintótica del algoritmo findMax anterior es Ω(1), donde n es el tamaño de la matriz de entrada.
En esta publicación, hemos visto cómo se puede usar el análisis asintótico para describir la complejidad computacional de los algoritmos. También hemos visto cómo las tres formas comunes de representar la complejidad asintótica de un algoritmo son la notación Big-O, la notación Big-Θ y la notación Big-Ω.