Looking for algorithm Answers? Try Ask4KnowledgeBase
Looking for algorithm Keywords? Try Ask4Keywords

algorithmNotación Big-O


Observaciones

Definición

La notación Big-O es en su corazón una notación matemática, utilizada para comparar la tasa de convergencia de funciones. Sean n -> f(n) y n -> g(n) funciones definidas sobre los números naturales. Luego decimos que f = O(g) si y solo si f(n)/g(n) está limitada cuando n se acerca al infinito. En otras palabras, f = O(g) si y solo si existe una constante A, tal que para todos n, f(n)/g(n) <= A

En realidad, el alcance de la notación Big-O es un poco más amplio en matemáticas, pero por simplicidad lo he reducido a lo que se usa en el análisis de complejidad de algoritmos: funciones definidas en los naturales, que tienen valores distintos de cero, y el caso de n creciente hasta el infinito.

Qué significa eso ?

Tomemos el caso de f(n) = 100n^2 + 10n + 1 g(n) = n^2 . Es bastante claro que ambas funciones tienden a infinito ya que n tiende a infinito. Pero a veces, saber el límite no es suficiente, y también queremos saber la velocidad a la que las funciones se acercan a su límite. Nociones como Big-O ayudan a comparar y clasificar funciones por su velocidad de convergencia.

Averigüemos si f = O(g) aplicando la definición. Tenemos f(n)/g(n) = 100 + 10/n + 1/n^2 . Desde 10/n es 10 cuando n es 1 y está disminuyendo, y desde 1/n^2 es 1 cuando n es 1 y también está disminuyendo, hemos f f(n)/g(n) <= 100 + 10 + 1 = 111 . La definición se cumple porque hemos encontrado un límite de f(n)/g(n) (111) y por tanto f = O(g) (decimos que f es un Big-O de n^2 ).

Esto significa que f tiende a infinito aproximadamente a la misma velocidad que g. Ahora bien, esto puede parecer algo extraño de decir, porque lo que hemos encontrado es que f es a lo sumo 111 veces más grande que g, o en otras palabras, cuando g crece en 1, f crece como máximo en 111. Puede parecer que en crecimiento 111 veces más rápido no es "aproximadamente la misma velocidad". Y, de hecho, la notación Big-O no es una forma muy precisa de clasificar la velocidad de convergencia de la función, por lo que en matemáticas usamos la relación de equivalencia cuando queremos una estimación precisa de la velocidad. Pero a los efectos de separar algoritmos en clases de gran velocidad, Big-O es suficiente. No necesitamos separar las funciones que crecen un número fijo de veces más rápido que las otras, sino solo las funciones que crecen infinitamente más rápido que las otras. Por ejemplo, si tomamos h(n) = n^2*log(n) , vemos que h(n)/g(n) = log(n) que tiende a infinito con n, por lo que h no es O (n ^ 2), porque h crece infinitamente más rápido que n ^ 2.

Ahora necesito hacer una nota al margen: es posible que haya notado que si f = O(g) g = O(h) , entonces f = O(h) . Por ejemplo, en nuestro caso, tenemos f = O(n^3) , y f = O(n^4) ... En el análisis de complejidad de algoritmos, frecuentemente decimos que f = O(g) significa que f = O(g) y g = O(f) , que puede entenderse como "g es el Big-O más pequeño para f". En matemáticas decimos que tales funciones son Big-Thetas entre sí.

Cómo se usa ?

Al comparar el rendimiento del algoritmo, nos interesa la cantidad de operaciones que realiza un algoritmo. Esto se llama complejidad del tiempo . En este modelo, consideramos que cada operación básica (suma, multiplicación, comparación, asignación, etc.) toma una cantidad de tiempo fija, y contamos el número de dichas operaciones. Por lo general, podemos expresar este número en función del tamaño de la entrada, que llamamos n. Y lamentablemente, este número generalmente crece hasta el infinito con n (si no lo hace, decimos que el algoritmo es O (1)). Separamos nuestros algoritmos en clases de gran velocidad definidas por Big-O: cuando hablamos de un "algoritmo O (n ^ 2)", queremos decir que la cantidad de operaciones que realiza, expresada como una función de n, es una O ( n ^ 2). Esto dice que nuestro algoritmo es aproximadamente tan rápido como un algoritmo que haría una cantidad de operaciones igual al cuadrado del tamaño de su entrada, o más rápido . La parte "o más rápida" está ahí porque usé Big-O en lugar de Big-Theta, pero generalmente la gente dirá que Big-O quiere decir Big-Theta.

Cuando contamos las operaciones, generalmente consideramos el peor de los casos: por ejemplo, si tenemos un bucle que puede ejecutarse como máximo n veces y que contiene 5 operaciones, el número de operaciones que contamos es 5n. También es posible considerar la complejidad del caso promedio.

Nota rápida: un algoritmo rápido es uno que realiza pocas operaciones, por lo que si el número de operaciones crece infinitamente más rápido , entonces el algoritmo es más lento : O (n) es mejor que O (n ^ 2).

También a veces estamos interesados ​​en la complejidad espacial de nuestro algoritmo. Para esto, consideramos el número de bytes en la memoria ocupada por el algoritmo como una función del tamaño de la entrada, y usamos Big-O de la misma manera.

Notación Big-O Ejemplos relacionados