Rob Bell tiene una entrada en su blog (A beginner’s guide to Big O notation) con la explicación y ejemplos más sencillos que he visto acerca de la “Cota Superior Asintótica” (Notación O Grande) mejor conocida como “Big O notation” en Inglés.
A continuación me he permitido hacer una traducción libre al Español del artículo creado por Rob Bell.
Big O notation se utiliza en informática para describir el rendimiento o la complejidad de un algoritmo. Big O describe específicamente el peor de los casos, y se puede utilizar para describir el tiempo de ejecución requerido o el espacio utilizado (por ejemplo en la memoria en el disco) por un algoritmo.
Cualquiera que haya leído Programming Pearls o cualquier otro libro Ciencias de la Computación y no tiene bases en Matemáticas habrá chocado contra un muro cuando llegaron los capítulos que mencionan O(N log N) u otra sintaxis aparentemente descabellada. Esperemos que este artículo le ayude a obtener una comprensión de los conceptos básicos de Big O y logaritmos.
Como programador primero y matemático segúndo (o tal vez tercero o cuarto) he encontrado la mejor manera de entender Big O bien era producir algunos ejemplos de código. Por lo tanto, a continuación son algunas órdenes comunes de crecimiento, junto con descripciones y ejemplos cuando sea posible.
O(1) describe un algoritmo que siempre va a ejecutar en el mismo tiempo (o espacio), independientemente del tamaño del conjunto de datos de entrada.
bool IsFirstElementNull(IList<string> elements)
{
return elements[0] == null;
}
O(N) describe un algoritmo cuyo rendimiento va a crecer de forma lineal y en proporción directa con el tamaño del conjunto de datos de entrada. El siguiente ejemplo también demuestra cómo Big O favorece el rendimiento en el peor de los casos; una cadena que cumpla la condición puede ser encontrada durante cualquiera de las iteraciónes del bucle for y salir de la función antes, pero ‘Big O notation’ siempre asumirá el límite superior en el que el algoritmo llevará a cabo el número máximo de iteraciones.
bool ContainsValue(IList<string> elements, string value)
{
foreach (var element in elements)
{
if (element == value) return true;
}
return false;
}
O(N²) representa un algoritmo cuyo rendimiento es directamente proporcional al cuadrado del tamaño del conjunto de datos de entrada. Esto es común con algoritmos que implican iteraciones anidadas más de la serie de datos. Iteraciones anidadas más profundas resultarán en O(N³), O(N⁴), etc.
bool ContainsDuplicates(IList<string> elements)
{
for (var outer = 0; outer < elements.Count; outer++)
{
for (var inner = 0; inner < elements.Count; inner++)
{
// Don't compare with self
if (outer == inner) continue;
if (elements[outer] == elements[inner]) return true;
}
}
return false;
}
O(2ᴺ) denota un algoritmo cuyo crecimiento se duplica con cada adición al conjunto de datos de entrada. La curva de crecimiento de una función O(2ᴺ) es exponencial - partiendo muy poco profunda, seguida de un aumento meteórica. Un ejemplo de una función O(2ᴺ) es el cálculo recursivo de los números de Fibonacci:
int Fibonacci(int number)
{
if (number <= 1) return number;
return Fibonacci(number - 2) + Fibonacci(number - 1);
}
Los logaritmos son un poco más difícil de explicar así que voy a utilizar un ejemplo común:
La búsqueda binaria es una técnica utilizada para buscar los conjuntos de datos ordenados. Funciona seleccionando el elemento medio del conjunto de datos, esencialmente la mediana, y la compara con un valor objetivo. Si los valores coinciden regresará éxito. Si el valor objetivo es mayor que el valor del elemento de prueba que tomará la mitad superior del conjunto de datos y realizará la misma operación en contra de ella. Asimismo, si el valor objetivo es inferior al valor del elemento de prueba y se llevará a cabo la operación contra la mitad inferior. Continuará hasta reducir a la mitad el conjunto de datos con cada iteración hasta que se haya encontrado el valor o hasta que ya no se puede dividir el conjunto de datos.
Este tipo de algoritmo se describe como O(log N). La reducción a la mitad iterativa de conjuntos de datos se describe en el ejemplo de búsqueda binaria produce una curva de crecimiento que alcanza el máximo al principio y lentamente se aplana conforme el tamaño de los conjuntos de datos aumentan, por ejemplo, un conjunto de datos de entrada que contiene 10 artículos toma un segundo para completar, un conjunto de datos que contiene 100 artículos tarda dos segundos, y un conjunto de datos que contiene 1000 elementos se llevará tres segundos. Duplicando el tamaño del conjunto de datos de entrada tienen poco efecto sobre su crecimiento como después de una sola iteración del algoritmo del conjunto de datos se reduce a la mitad, por lo que a la par de un conjunto de datos de entrada establece la mitad del tamaño. Esto hace que los algoritmos de búsqueda binaria sean extremadamente eficientes cuando se trata de grandes conjuntos de datos.
Este artículo sólo cubre los conceptos básicos de Big O y logaritmos. Para una explicación más detallada echar un vistazo a sus respectivas entradas en Wikipedia: Big O Notation, logaritmos.
Artículo original en Inglés creado por Rob Bell, públicado el día 23 de Junio del 2009, traducido libremente al Español por Abraham Estrada.
https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/