Explicación de la notación Big O: complejidad espacial y temporal

¿Realmente entiendes Big O? Si es así, esto refrescará su comprensión antes de una entrevista. Si no es así, no se preocupe, venga y únase a nosotros para algunos esfuerzos en informática.

Si usted ha tomado algunos cursos relacionados con el algoritmo, lo que has oído del término notación O grande . Si no lo ha hecho, lo repasaremos aquí y luego obtendremos una comprensión más profunda de lo que realmente es.

La notación Big O es una de las herramientas más fundamentales para que los científicos informáticos analicen el costo de un algoritmo. También es una buena práctica que los ingenieros de software comprendan en profundidad.

Este artículo está escrito asumiendo que ya ha abordado algún código. Además, algunos materiales en profundidad también requieren fundamentos matemáticos de secundaria y, por lo tanto, pueden ser un poco menos cómodos para los principiantes totales. Pero si estás listo, ¡comencemos!

En este artículo, tendremos una discusión en profundidad sobre la notación Big O. Comenzaremos con un algoritmo de ejemplo para abrir nuestra comprensión. Luego, entraremos un poco en las matemáticas para tener una comprensión formal. Después de eso, repasaremos algunas variaciones comunes de la notación Big O. Al final, discutiremos algunas de las limitaciones de Big O en un escenario práctico. Puede encontrar una tabla de contenido a continuación.

Tabla de contenido

  1. ¿Qué es la notación Big O y por qué es importante?
  2. Definición formal de la notación Big O
  3. Big O, Little O, Omega y Theta
  4. Comparación de complejidad entre Big Os típicos
  5. Complejidad de tiempo y espacio
  6. Complejidad óptima, media, peor y esperada
  7. Por que Big O no importa
  8. En el final…

Entonces empecemos.

1. ¿Qué es la notación Big O y por qué es importante?

“La notación Big O es una notación matemática que describe el comportamiento limitante de una función cuando el argumento tiende hacia un valor particular o infinito. Es un miembro de una familia de notaciones inventadas por Paul Bachmann, Edmund Landau y otros, llamadas colectivamente notación de Bachmann-Landau o notación asintótica ”. Definición de Wikipedia de notación Big O

En palabras sencillas, la notación Big O describe la complejidad de su código utilizando términos algebraicos.

Para entender qué es la notación Big O, podemos echar un vistazo a un ejemplo típico, O (n²) , que generalmente se pronuncia "Big O al cuadrado" . La letra "n" aquí representa el tamaño de entrada , y la función "g (n) = n²" dentro de la "O ()" nos da una idea de cuán complejo es el algoritmo con respecto al tamaño de entrada.

Un algoritmo típico que tiene la complejidad de O (n²) sería el algoritmo de clasificación de selección . La clasificación por selección es un algoritmo de clasificación que recorre la lista para garantizar que cada elemento del índice i sea ​​el i-ésimo elemento más pequeño / más grande de la lista. El CODEPEN a continuación ofrece un ejemplo visual de ello.

El algoritmo se puede describir mediante el siguiente código. Para asegurarse de que el i-ésimo elemento sea el i-ésimo elemento más pequeño de la lista, este algoritmo primero recorre la lista con un bucle for. Luego, para cada elemento, usa otro bucle for para encontrar el elemento más pequeño en la parte restante de la lista.

SelectionSort(List) { for(i from 0 to List.Length) { SmallestElement = List[i] for(j from i to List.Length) { if(SmallestElement > List[j]) { SmallestElement = List[j] } } Swap(List[i], SmallestElement) } }

En este escenario, consideramos la variable List como la entrada, por lo que el tamaño de entrada n es el número de elementos dentro de List . Suponga que la instrucción if y la asignación de valor limitada por la instrucción if requieren un tiempo constante. Luego, podemos encontrar la notación O grande para la función SelectionSort analizando cuántas veces se ejecutan las declaraciones.

Primero, el ciclo for interno ejecuta las declaraciones dentro de n veces. Y luego, después de que se incrementa i , el bucle for interno se ejecuta n-1 veces ... ... hasta que se ejecuta una vez, entonces ambos bucles for alcanzan sus condiciones de terminación.

Esto en realidad termina dándonos una suma geométrica, y con algunas matemáticas de la escuela secundaria, encontraríamos que el ciclo interno se repetirá 1 + 2… + n veces, lo que equivale a n (n-1) / 2 veces. Si multiplicamos esto, terminaremos obteniendo n² / 2-n / 2.

Cuando calculamos la notación O grande, solo nos preocupan los términos dominantes y no nos importan los coeficientes. Por lo tanto, tomamos el n² como nuestra gran O final. Lo escribimos como O (n²), que nuevamente se pronuncia "Big O al cuadrado" .

Ahora se estará preguntando, ¿de qué se trata este “término dominante” ? ¿Y por qué no nos preocupan los coeficientes? No se preocupe, los repasaremos uno por uno. Puede ser un poco difícil de entender al principio, pero todo tendrá mucho más sentido a medida que lea la siguiente sección.

2. Definición formal de la notación Big O

Érase una vez un rey indio que quería recompensar a un sabio por su excelencia. El sabio no pidió nada más que un poco de trigo que llenaría un tablero de ajedrez.

Pero aquí estaban sus reglas: en la primera ficha quiere 1 grano de trigo, luego 2 en la segunda ficha, luego 4 en la siguiente ... cada ficha del tablero de ajedrez debe llenarse con el doble de granos que la anterior. uno. El rey ingenuo estuvo de acuerdo sin dudarlo, pensando que sería una exigencia trivial de cumplir, hasta que realmente continuó y lo probó ...

Entonces, ¿cuántos granos de trigo le debe el rey al sabio? Sabemos que un tablero de ajedrez tiene 8 cuadrados por 8 cuadrados, que suman 64 fichas, por lo que la ficha final debe tener 2⁶⁴ granos de trigo. Si realiza un cálculo en línea, terminará obteniendo 1.8446744 * 10¹⁹, es decir, aproximadamente 18 seguido de 18 ceros. Suponiendo que cada grano de trigo pesa 0,01 gramos, eso nos da 184,467,440,737 toneladas de trigo. Y 184 mil millones de toneladas es bastante, ¿no?

Los números crecen bastante rápido más tarde para un crecimiento exponencial, ¿no es así? La misma lógica se aplica a los algoritmos informáticos. Si los esfuerzos necesarios para realizar una tarea crecen exponencialmente con respecto al tamaño de entrada, puede llegar a ser enormemente grande.

Ahora el cuadrado de 64 es 4096. Si agrega ese número a 2⁶⁴, se perderá fuera de los dígitos significativos. Por eso, cuando miramos la tasa de crecimiento, solo nos interesan los términos dominantes. Y dado que queremos analizar el crecimiento con respecto al tamaño de entrada, los coeficientes que solo multiplican el número en lugar de crecer con el tamaño de entrada no contienen información útil.

A continuación se muestra la definición formal de Big O:

La definición formal es útil cuando necesita realizar una prueba matemática. Por ejemplo, la complejidad de tiempo para el ordenamiento por selección se puede definir mediante la función f (n) = n² / 2-n / 2 como hemos discutido en la sección anterior.

Si permitimos que nuestra función g (n) sea n², podemos encontrar una constante c = 1 y una N₀ = 0, y siempre que N> N₀, N² siempre será mayor que N² / 2-N / 2. Podemos probar esto fácilmente restando N² / 2 de ambas funciones, entonces podemos ver fácilmente que N² / 2> -N / 2 es verdadero cuando N> 0. Por lo tanto, podemos llegar a la conclusión de que f (n) = O (n²), en el otro tipo de selección es "O grande al cuadrado".

You might have noticed a little trick here. That is, if you make g(n) grow supper fast, way faster than anything, O(g(n)) will always be great enough. For example, for any polynomial function, you can always be right by saying that they are O(2ⁿ) because 2ⁿ will eventually outgrow any polynomials.

Mathematically, you are right, but generally when we talk about Big O, we want to know the tight bound of the function. You will understand this more as you read through the next section.

But before we go, let’s test your understanding with the following question. The answer will be found in later sections so it won’t be a throw away.

Pregunta: Una imagen está representada por una matriz 2D de píxeles. Si usa un bucle for anidado para iterar a través de cada píxel (es decir, tiene un bucle for que atraviesa todas las columnas, luego otro bucle for en el interior para recorrer todas las filas), ¿cuál es la complejidad temporal del algoritmo cuando el ¿La imagen se considera como entrada?

3. Big O, Little O, Omega y Theta

Big O: "f (n) es O (g (n))" sif para algunas constantes cy N₀, f (N) ≤ cg (N) para todo N> N₀Omega: "f (n) es Ω (g ( n)) ”sif para algunas constantes c y N₀, f (N) ≥ cg (N) para todo N> N₀Theta:“ f (n) es Θ (g (n)) ”si f (n) es O (g (n)) yf (n) es Ω (g (n)) Pequeña O: "f (n) es o (g (n))" si f (n) es O (g (n)) y f ( n) no es Θ (g (n)) - Definición formal de Big O, Omega, Theta y Little O

En palabras sencillas:

  • Big O (O()) describes the upper bound of the complexity.
  • Omega (Ω()) describes the lower bound of the complexity.
  • Theta (Θ()) describes the exact bound of the complexity.
  • Little O (o()) describes the upper bound excluding the exact bound.

For example, the function g(n) = n² + 3n is O(n³), o(n⁴), Θ(n²) and Ω(n). But you would still be right if you say it is Ω(n²) or O(n²).

Generally, when we talk about Big O, what we actually meant is Theta. It is kind of meaningless when you give an upper bound that is way larger than the scope of the analysis. This would be similar to solving inequalities by putting ∞ on the larger side, which will almost always make you right.

But how do we determine which functions are more complex than others? In the next section you will be reading, we will learn that in detail.

4. Complexity Comparison Between Typical Big Os

When we are trying to figure out the Big O for a particular function g(n), we only care about the dominant term of the function. The dominant term is the term that grows the fastest.

For example, n² grows faster than n, so if we have something like g(n) = n² + 5n + 6, it will be big O(n²). If you have taken some calculus before, this is very similar to the shortcut of finding limits for fractional polynomials, where you only care about the dominant term for numerators and denominators in the end.

But which function grows faster than the others? There are actually quite a few rules.

1. O(1) has the least complexity

Often called “constant time”, if you can create an algorithm to solve the problem in O(1), you are probably at your best. In some scenarios, the complexity may go beyond O(1), then we can analyze them by finding its O(1/g(n)) counterpart. For example, O(1/n) is more complex than O(1/n²).

2. O(log(n)) is more complex than O(1), but less complex than polynomials

As complexity is often related to divide and conquer algorithms, O(log(n)) is generally a good complexity you can reach for sorting algorithms. O(log(n)) is less complex than O(√n), because the square root function can be considered a polynomial, where the exponent is 0.5.

3. Complexity of polynomials increases as the exponent increases

For example, O(n⁵) is more complex than O(n⁴). Due to the simplicity of it, we actually went over quite many examples of polynomials in the previous sections.

4. Exponentials have greater complexity than polynomials as long as the coefficients are positive multiples of n

O(2ⁿ) is more complex than O(n⁹⁹), but O(2ⁿ) is actually less complex than O(1). We generally take 2 as base for exponentials and logarithms because things tends to be binary in Computer Science, but exponents can be changed by changing the coefficients. If not specified, the base for logarithms is assumed to be 2.

5. Factorials have greater complexity than exponentials

If you are interested in the reasoning, look up the Gamma function, it is an analytic continuation of a factorial. A short proof is that both factorials and exponentials have the same number of multiplications, but the numbers that get multiplied grow for factorials, while remaining constant for exponentials.

6. Multiplying terms

When multiplying, the complexity will be greater than the original, but no more than the equivalence of multiplying something that is more complex. For example, O(n * log(n)) is more complex than O(n) but less complex than O(n²), because O(n²) = O(n * n) and n is more complex than log(n).

To test your understanding, try ranking the following functions from the most complex to the lease complex. The solutions with detailed explanations can be found in a later section as you read. Some of them are meant to be tricky and may require some deeper understanding of math. As you get to the solution, you will understand them more.

Pregunta: Clasifique las siguientes funciones desde las más complejas hasta las más complejas de arrendamiento. Solución a la pregunta de la Sección 2: En realidad, estaba destinada a ser una pregunta capciosa para probar su comprensión. La pregunta intenta hacerle responder O (n²) porque hay un ciclo for anidado. Sin embargo, se supone que n es el tamaño de entrada. Dado que la matriz de imágenes es la entrada y cada píxel se repitió solo una vez, la respuesta es en realidad O (n). La siguiente sección repasará más ejemplos como este.

5. Complejidad de tiempo y espacio

So far, we have only been discussing the time complexity of the algorithms. That is, we only care about how much time it takes for the program to complete the task. What also matters is the space the program takes to complete the task. The space complexity is related to how much memory the program will use, and therefore is also an important factor to analyze.

The space complexity works similarly to time complexity. For example, selection sort has a space complexity of O(1), because it only stores one minimum value and its index for comparison, the maximum space used does not increase with the input size.

Some algorithms, such as bucket sort, have a space complexity of O(n), but are able to chop down the time complexity to O(1). Bucket sort sorts the array by creating a sorted list of all the possible elements in the array, then increments the count whenever the element is encountered. In the end the sorted array will be the sorted list elements repeated by their counts.

6. Best, Average, Worst, Expected Complexity

The complexity can also be analyzed as best case, worst case, average case and expected case.

Let’s take insertion sort, for example. Insertion sort iterates through all the elements in the list. If the element is larger than its previous element, it inserts the element backwards until it is larger than the previous element.

If the array is initially sorted, no swap will be made. The algorithm will just iterate through the array once, which results a time complexity of O(n). Therefore, we would say that the best-case time complexity of insertion sort is O(n). A complexity of O(n) is also often called linear complexity.

Sometimes an algorithm just has bad luck. Quick sort, for example, will have to go through the list in O(n) time if the elements are sorted in the opposite order, but on average it sorts the array in O(n * log(n)) time. Generally, when we evaluate time complexity of an algorithm, we look at their worst-case performance. More on that and quick sort will be discussed in the next section as you read.

The average case complexity describes the expected performance of the algorithm. Sometimes involves calculating the probability of each scenarios. It can get complicated to go into the details and therefore not discussed in this article. Below is a cheat-sheet on the time and space complexity of typical algorithms.

Solution to Section 4 Question:

By inspecting the functions, we should be able to immediately rank the following polynomials from most complex to lease complex with rule 3. Where the square root of n is just n to the power of 0.5.

Then by applying rules 2 and 6, we will get the following. Base 3 log can be converted to base 2 with log base conversions. Base 3 log still grows a little bit slower then base 2 logs, and therefore gets ranked after.

The rest may look a little bit tricky, but let’s try to unveil their true faces and see where we can put them.

First of all, 2 to the power of 2 to the power of n is greater than 2 to the power of n, and the +1 spices it up even more.

And then since we know 2 to the power of log(n) with based 2 is equal to n, we can convert the following. The log with 0.001 as exponent grows a little bit more than constants, but less than almost anything else.

The one with n to the power of log(log(n)) is actually a variation of the quasi-polynomial, which is greater than polynomial but less than exponential. Since log(n) grows slower than n, the complexity of it is a bit less. The one with the inverse log converges to constant, as 1/log(n) diverges to infinity.

Los factoriales se pueden representar mediante multiplicaciones y, por lo tanto, se pueden convertir en sumas fuera de la función logarítmica. El "n elige 2" se puede convertir en un polinomio con un término cúbico siendo el más grande.

Y finalmente, podemos clasificar las funciones desde las más complejas hasta las menos complejas.

Por qué BigO no importa

!!! - ADVERTENCIA - !!! Los contenidos discutidos aquí generalmente no son aceptados por la mayoría de los programadores del mundo. Discútelo bajo su propio riesgo en una entrevista. La gente de hecho escribió en blogs sobre cómo fallaron en sus entrevistas de Google porque cuestionaron la autoridad, como aquí. !!! - ADVERTENCIA - !!!

Since we have previously learned that the worst case time complexity for quick sort is O(n²), but O(n * log(n)) for merge sort, merge sort should be faster — right? Well you probably have guessed that the answer is false. The algorithms are just wired up in a way that makes quick sort the “quick sort”.

To demonstrate, check out this trinket.io I made. It compares the time for quick sort and merge sort. I have only managed to test it on arrays with a length up to 10000, but as you can see so far, the time for merge sort grows faster than quick sort. Despite quick sort having a worse case complexity of O(n²), the likelihood of that is really low. When it comes to the increase in speed quick sort has over merge sort bounded by the O(n * log(n)) complexity, quick sort ends up with a better performance in average.

I have also made the below graph to compare the ratio between the time they take, as it is hard to see them at lower values. And as you can see, the percentage time taken for quick sort is in a descending order.

The moral of the story is, Big O notation is only a mathematical analysis to provide a reference on the resources consumed by the algorithm. Practically, the results may be different. But it is generally a good practice trying to chop down the complexity of our algorithms, until we run into a case where we know what we are doing.

In the end…

I like coding, learning new things and sharing them with the community. If there is anything in which you are particularly interested, please let me know. I generally write on web design, software architecture, mathematics and data science. You can find some great articles I have written before if you are interested in any of the topics above.

Hope you have a great time learning computer science!!!