1. Información general
En este tutorial, hablaremos sobre lo que significa Big O Notation. Revisaremos algunos ejemplos para investigar su efecto en el tiempo de ejecución de su código.
2. La intuición de la notación Big O
A menudo escuchamos el desempeño de un algoritmo descrito usando Big O Notation.
El estudio del rendimiento de los algoritmos, o complejidad algorítmica, entra en el campo del análisis de algoritmos. El análisis de algoritmos responde a la pregunta de cuántos recursos, como espacio en disco o tiempo, consume un algoritmo.
Consideraremos el tiempo como un recurso. Normalmente, cuanto menos tiempo tarde en completarse un algoritmo, mejor.
3. Algoritmos de tiempo constante - O (1)
¿Cómo afecta este tamaño de entrada de un algoritmo a su tiempo de ejecución? La clave para comprender Big O es comprender las tasas a las que las cosas pueden crecer. La tasa en cuestión aquí es el tiempo necesario por tamaño de entrada.
Considere esta simple pieza de código:
int n = 1000; System.out.println("Hey - your input is: " + n);Claramente, no importa lo que sea n arriba. Este fragmento de código tarda una cantidad constante de tiempo en ejecutarse. No depende del tamaño de n.
Similar:
int n = 1000; System.out.println("Hey - your input is: " + n); System.out.println("Hmm.. I'm doing more stuff with: " + n); System.out.println("And more: " + n);El ejemplo anterior también es un tiempo constante. Incluso si tarda 3 veces más en ejecutarse, no depende del tamaño de la entrada, n. Denotamos algoritmos de tiempo constante como sigue: O (1) . Tenga en cuenta que O (2) , O (3) o incluso O (1000) significarían lo mismo.
No nos importa exactamente cuánto tiempo tarda en ejecutarse, solo que lleva un tiempo constante.
4. Algoritmos de tiempo logarítmico - O (log n)
Los algoritmos de tiempo constante son (asintóticamente) los más rápidos. El tiempo logarítmico es el siguiente más rápido. Desafortunadamente, son un poco más difíciles de imaginar.
Un ejemplo común de un algoritmo de tiempo logarítmico es el algoritmo de búsqueda binaria. Para ver cómo implementar la búsqueda binaria en Java, haga clic aquí.
Lo importante aquí es que el tiempo de ejecución crece en proporción al logaritmo de la entrada (en este caso, logaritmo a la base 2):
for (int i = 1; i < n; i = i * 2){ System.out.println("Hey - I'm busy looking at: " + i); }Si n es 8, la salida será la siguiente:
Hey - I'm busy looking at: 1 Hey - I'm busy looking at: 2 Hey - I'm busy looking at: 4Nuestro algoritmo simple corrió log (8) = 3 veces.
5. Algoritmos de tiempo lineal - O (n)
Después de los algoritmos de tiempo logarítmico, obtenemos la siguiente clase más rápida: algoritmos de tiempo lineal.
Si decimos que algo crece linealmente, queremos decir que crece directamente proporcionalmente al tamaño de sus entradas.
Piense en un bucle for simple:
for (int i = 0; i < n; i++) { System.out.println("Hey - I'm busy looking at: " + i); }¿Cuántas veces se ejecuta este bucle for? n veces, ¡por supuesto! No sabemos exactamente cuánto tiempo tardará en ejecutarse, y no nos preocupamos por eso.
Lo que sí sabemos es que el algoritmo simple presentado anteriormente crecerá linealmente con el tamaño de su entrada.
Preferiríamos un tiempo de ejecución de 0.1n que (1000n + 1000) , pero ambos siguen siendo algoritmos lineales; ambos crecen directamente en proporción al tamaño de sus insumos.
Nuevamente, si el algoritmo se cambió a lo siguiente:
for (int i = 0; i < n; i++) { System.out.println("Hey - I'm busy looking at: " + i); System.out.println("Hmm.. Let's have another look at: " + i); System.out.println("And another: " + i); }El tiempo de ejecución aún sería lineal en el tamaño de su entrada, n . Denotamos algoritmos lineales como sigue: O (n) .
Al igual que con los algoritmos de tiempo constante, no nos importan los detalles del tiempo de ejecución. O (2n + 1) es lo mismo que O (n) , ya que Big O Notation se ocupa del crecimiento de los tamaños de entrada.
6. Algoritmos de tiempo N Log N - O (n log n)
n log n es la siguiente clase de algoritmos. El tiempo de ejecución crece en proporción an log n de la entrada:
for (int i = 1; i <= n; i++){ for(int j = 1; j < n; j = j * 2) { System.out.println("Hey - I'm busy looking at: " + i + " and " + j); } } Por ejemplo, si n es 8, entonces este algoritmo ejecutará 8 * log (8) = 8 * 3 = 24 veces. Si tenemos una desigualdad estricta o no en el bucle for es irrelevante por el bien de una notación Big O.
7. Algoritmos de tiempo polinomial - O (np)
A continuación, tenemos algoritmos de tiempo polinomial. Estos algoritmos son incluso más lentos que los algoritmos n log n .
El término polinomio es un término general que contiene funciones cuadráticas (n2) , cúbicas (n3) , cuarticas (n4) , etc. Lo que es importante saber es que O (n2) es más rápido que O (n3), que es más rápido que O (n4) , etc.
Echemos un vistazo a un ejemplo simple de un algoritmo de tiempo cuadrático:
for (int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { System.out.println("Hey - I'm busy looking at: " + i + " and " + j); } } Este algoritmo se ejecutará 82 = 64 veces. Tenga en cuenta que si anidamos otro bucle for, esto se convertiría en un algoritmo O (n3) .
8. Algoritmos de tiempo exponencial - O ( k n)
Ahora nos adentramos en territorio peligroso; estos algoritmos crecen en proporción a algún factor exponencializado por el tamaño de entrada.
Por ejemplo, los algoritmos O (2n) se duplican con cada entrada adicional. Entonces, si n = 2 , estos algoritmos se ejecutarán cuatro veces; si n = 3 , se ejecutarán ocho veces (algo así como lo opuesto a los algoritmos de tiempo logarítmico).
O(3n) algorithms triple with every additional input, O(kn) algorithms will get k times bigger with every additional input.
Let's have a look at a simple example of an O(2n) time algorithm:
for (int i = 1; i <= Math.pow(2, n); i++){ System.out.println("Hey - I'm busy looking at: " + i); }This algorithm will run 28 = 256 times.
9. Factorial Time Algorithms – O(n!)
In most cases, this is pretty much as bad as it'll get. This class of algorithms has a run time proportional to the factorial of the input size.
A classic example of this is solving the traveling salesman problem using a brute-force approach to solve it.
An explanation of the solution to the traveling salesman problem is beyond the scope of this article.
Instead, let's look at a simple O(n!) algorithm, as in the previous sections:
for (int i = 1; i <= factorial(n); i++){ System.out.println("Hey - I'm busy looking at: " + i); }where factorial(n) simply calculates n!. If n is 8, this algorithm will run 8! = 40320 times.
10. Asymptotic Functions
Big O is what is known as an asymptotic function. All this means, is that it concerns itself with the performance of an algorithm at the limit – i.e. – when lots of input is thrown at it.
Big O doesn't care about how well your algorithm does with inputs of small size. It's concerned with large inputs (think sorting a list of one million numbers vs. sorting a list of 5 numbers).
Another thing to note is that there are other asymptotic functions. Big Θ (theta) and Big Ω (omega) also both describes algorithms at the limit (remember, the limit this just means for huge inputs).
To understand the differences between these 3 important functions, we first need to know that each of Big O, Big Θ, and Big Ω describes a set (i.e., a collection of elements).
Here, the members of our sets are algorithms themselves:
- Big O describes the set of all algorithms that run no worse than a certain speed (it's an upper bound)
- Conversely, Big Ω describes the set of all algorithms that run no better than a certain speed (it's a lower bound)
- Finalmente, Big Θ describe el conjunto de todos los algoritmos que se ejecutan a una cierta velocidad (es como igualdad)
Las definiciones que hemos puesto arriba no son matemáticamente precisas, pero ayudarán a nuestra comprensión.
Por lo general, escucharás las cosas descritas usando Big O , pero no está de más saber sobre Big Θ y Big Ω.
11. Conclusión
En este artículo, discutimos la notación Big O y cómo comprender la complejidad de un algoritmo puede afectar el tiempo de ejecución de su código.
Aquí se puede encontrar una gran visualización de las diferentes clases de complejidad.
Como de costumbre, los fragmentos de código de este tutorial se pueden encontrar en GitHub.