La gran notación Oh no menciona el valor constante

13

Soy programador y acabo de empezar a leer Algoritmos. No estoy completamente convencido con las anotaciones, a saber, Bog Oh, Big Omega y Big Theta. La razón es, por definición de Big Oh, que establece que debería haber una función g (x) tal que siempre sea mayor o igual que f (x). O f (x) <= cn para todos los valores de n> n0.

¿Por qué no mencionamos el valor constante en la definición? Por ejemplo, digamos una función 6n + 4, la denotamos como O (n). Pero no es cierto que la definición sea válida para todo valor constante. Esto es válido solo cuando c> = 10 yn> = 1. Para valores menores de c que 6, el valor de n0 aumenta. Entonces, ¿por qué no mencionamos el valor constante como parte de la definición?

Pradeep
fuente
44
¿Cómo propones representar el valor constante exactamente?
Daniel B
1
Llevando su punto un paso más allá, cualquier función de terminación es O (1) si enlaza n.
Brian

Respuestas:

23

Hay varias razones, pero probablemente la más importante es que las constantes son una función de la implementación del algoritmo, no el algoritmo en sí. El orden de un algoritmo es útil para comparar algoritmos independientemente de su implementación.

El tiempo de ejecución real de una clasificación rápida normalmente cambiará si se implementa en C o Python o Scala o Postscript. Lo mismo se aplica para la clasificación de burbujas : el tiempo de ejecución variará ampliamente según la implementación.

Sin embargo, lo que no cambiará es el hecho de que, si todo lo demás es igual, a medida que el conjunto de datos aumenta, el tiempo requerido para ejecutar un ordenamiento de burbujas aumentará más rápido que el tiempo requerido para ejecutar el ordenamiento rápido en el caso típico, sin importar el idioma o la máquina se implementan con, asumiendo una implementación razonablemente correcta. Este simple hecho le permite hacer inferencias inteligentes sobre los algoritmos en sí mismos cuando los detalles concretos no están disponibles.

El orden de un algoritmo filtra factores que, si bien son importantes en las mediciones reales del mundo real, tienden a ser solo ruido al comparar algoritmos en abstracto.

tylerl
fuente
22

O (n) y otra notación de orden (típicamente) no está relacionada con el comportamiento de las funciones para valores pequeños. Se refiere al comportamiento de las funciones para valores muy grandes, es decir, límites a medida que n se mueve hacia el infinito.

Las constantes técnicamente son importantes, pero generalmente se abstraen, ya que una vez que n es lo suficientemente grande, el valor de c es completamente irrelevante. Si el valor de c es importante, podemos incluirlo en el análisis, pero a menos que las funciones que se comparan tengan factores constantes muy grandes o si la eficiencia es una preocupación especialmente importante, generalmente no lo son.

Ingeniero mundial
fuente
3
Por ejemplo, construir las pirámides es O (n), ordenar imágenes de ellas es O (n log n): en algún momento podría tener suficientes pirámides que tomaría más tiempo ordenar las imágenes que construir una nueva. ¡Pero solo para una gran cantidad de pirámides!
Martin Beckett
Buena respuesta, pero para un N dado, y dos algoritmos que típicamente caen en la misma "familia" de complejidades, puede tener mérito hacer exactamente lo que sugiere el OP e incluir al menos los coeficientes relativos. Un algoritmo lineal con el doble del número de instrucciones por elemento que otro podría denominarse * O * (2N) al segundo alg's * O * (N) para mostrar la diferencia relativa, porque para cualquier N, el primer algoritmo siempre será doble el tiempo de ejecución del segundo; sin embargo, cuando se compara con una función de una familia de complejidad diferente, como * O * (NlogN), los coeficientes no importan.
KeithS
10

La notación Big O según la definición establece que: La notación Big O se basa en la intuición de que para todos los valores n en y a la derecha de n ', el valor de f (n) está en o por debajo de cg (n). Las constantes tampoco importan cuando va a factores de alto valor (variables) (como n-cuadrado o n-cubo) ya que son solo las constantes y no las cantidades variables que pueden llegar a ser tan grandes como esos factores. A continuación se muestra el gráfico de notación Big-O.
For a given function g(n), we denote by O(g(n)) the set of functions:
O(g(n)) = {f(n): there exist positive constants c and n' such that 0<=f(n)<=c.g(n) for all n > n'}




ingrese la descripción de la imagen aquí

La esencia de esta notación está en el hecho " how lower is f(n) from c.g(n) and not when it starts becoming lower".

Vaibhav Agarwal
fuente
En ese caso, para cada O (n) también es Big theta de n ya que según la definición para alguna constante será un límite inferior y para alguna constante es un límite superior. por ejemplo, 6n + 4 también es un gran theta (n) ya que cuando c es menor que 10, siempre es el límite inferior. y cuando c es más de 10 es un límite superior. Entonces, ¿podemos decir que para cualquier notación Big Oh también es una gran theta?
Pradeep
1
Lo estás diciendo al revés: "Big Theta significa Big Oh". Y Big-Oh puede reemplazarse con Big-Theta para límites asintóticamente estrechos.
Vaibhav Agarwal
9

En el análisis de algoritmos, el orden de crecimiento es la abstracción clave y proporciona la velocidad a la que cambia el tiempo de ejecución a medida que cambia el tamaño de entrada. Digamos que un algoritmo tiene un tiempo de ejecución f(n) = 2n + 3. Ahora conectamos algún tamaño de entrada,

n = 10: 2 * 10 + 3 = 23

n = 100: 2 * 100 + 3 = 203

n = 10000: 2 * 10000 + 3 = 20003

n = 1000000: 2 * 1000000 + 3 = 2000003

n = 100000000 : 2 * 100000000 + 3 = 200000003

Como puede verse, el orden de crecimiento está determinado principalmente por la variable n; las constantes 2 y 3 son menos significativas y a medida que crece el tamaño de entrada se vuelven aún menos significativas para determinarlo. Esta es la razón por la cual en el análisis de algoritmos las constantes disminuyen a favor de la variable que determina el orden de crecimiento de una función.

El d
fuente
1

La noción completa de la notación Big-Oh es específicamente ignorar las constantes y presentar la parte más importante de la función que describe el tiempo de ejecución de un algoritmo.

Olvida la definición formal por un momento. ¿Cuál es la peor función (crecimiento más rápido) n^2 - 5000o 5000 n + 60000? Por nmenos de alrededor de 5000, la función lineal es mayor (y por lo tanto peor). Más allá de eso (¿valor exacto 5013?), La ecuación cuadrática es más grande.

Dado que hay más (bastantes más) números positivos mayores que 5000, consideramos que la función cuadrática es la función 'más grande' (peor) en general. La notación de orden (Big-Oh, etc.) impone que (siempre puede eliminar un aditivo y una constante multiplicativa usando esas definiciones).

Por supuesto, las cosas no siempre son simples. A veces uno no quiere saber esas constantes. ¿Cuál es el mejor tipo de inserción o de burbuja? Ambos son O(n^2). Pero uno realmente es mejor que el otro. Con un análisis más elaborado, uno puede obtener constantes como si se estuviera preguntando. Por lo general, es mucho más fácil calcular la función Big-Oh que una función más exacta.

Big-Oh ignora estas constantes para simplificar y facilitar las comparaciones más importantes. Nos gusta la notación porque generalmente no queremos saber sobre las constantes (en su mayoría irrelevantes).

Mitch
fuente
1

(dado que esta es una respuesta más larga, lea las negrillas para obtener un resumen )

Tomemos su ejemplo y avancemos paso a paso, entendiendo el propósito detrás de lo que estamos haciendo. Comenzamos con su función y el objetivo de encontrar su notación Big Oh:

f(n) = 6n+4

Primero, seamos O(g(n))la notación Big Oh que estamos tratando de encontrar f(n). A partir de la definición de Big Oh, necesitamos encontrar un simplificado g(n) donde existan algunas constantes cy n0donde c*g(n) >= f(n)sea ​​cierto para todos nlos mayores que n0.

Primero, elijamos g(n) = 6n + 4(lo que daría lugar O(6n+4)en Big Oh). En este caso, vemos que c = 1y cualquier valor de n0cumplirá con los requisitos matemáticos de nuestra definición de Big Oh, ya que g(n)siempre es igual a f(n):

c*g(n)      >=  f(n)    
1*(6n + 4)  >=  6n + 4    //True for all n's, so we don't need to pick an n0

En este punto, hemos cumplido los requisitos matemáticos. Si nos detenemosO(6n+4) , está claro que esto no es más útil que escribir f(n), por lo que perdería el verdadero propósito de la notación Big Oh: ¡comprender la complejidad temporal general de un algoritmo! Por lo tanto, pasemos al siguiente paso: la simplificación.

Primero, ¿podemos simplificar de 6nmodo que el Big Oh es O(4)? ¡No! (Ejercicio para el lector si no entiende por qué)

En segundo lugar, ¿podemos simplificar 4para que el Big Oh sea O(6n)? ¡Si! En ese caso g(n) = 6n, entonces:

c*g(n)    >=  f(n)
c*6n      >=  6n + 4     

En este punto, elijamos c = 2desde entonces que el lado izquierdo aumentará más rápido (en 12) que el lado derecho (en 6) para cada incremento de n.

2*6n      >=  6n + 4

Ahora necesitamos encontrar un punto positivo n0donde la ecuación anterior sea verdadera para todos nlos valores superiores a ese valor. Como ya sabemos que el lado izquierdo aumenta más rápido que el derecho, todo lo que tenemos que hacer es encontrar una solución positiva. Por lo tanto, dado que n0 = 2hace que lo anterior sea cierto, lo sabemos g(n)=6no O(6n)es una notación potencial de Big Oh f(n).

Ahora, ¿podemos simplificar 6para que el Big Oh sea O(n)? ¡Si! En ese caso g(n) = n, entonces:

c*g(n)      >=  f(n)    
c*n         >=  6n + 4    

Vamos a elegir c = 7ya que la izquierda aumentaría más rápido que la derecha.

7*n         >=  6n + 4

Vemos que lo anterior será cierto para todos nlos mayores o iguales a n0 = 4. Por lo tanto, O(n)es una notación potencial para Big Oh f(n). ¿Podemos simplificar g(n)más? No!

Finalmente, hemos descubierto que la notación Big Oh más simple f(n)es O(n). ¿Por qué pasamos por todo esto? Porque ahora sabemos que f(n)es lineal , ya que su notación Big Oh es de complejidad lineal O(n). ¡Lo bueno es que ahora podemos comparar la complejidad temporal de f(n)otros algoritmos! Por ejemplo, ahora sabemos que f(n)es comparable de tiempo-complejidad de las funciones h(n) = 123n + 72, i(n) = n, j(n) = .0002n + 1234, etc; porque al usar el mismo proceso de simplificación descrito anteriormente, todos tienen una complejidad lineal de tiempo O(n).

¡¡¡Dulce!!!

Briguy37
fuente
Hola buena explicacion Todavía tengo pocas dudas. 1. No podemos hacer 6n + 4 como O (4) ya que hay un valor variable 'n'. ¿Es esta la respuesta? 2. mientras que la simplificación eligió c = 7 y calculó correspondientemente n0 a 4. ¿Qué hizo para decidir c = 7 y no menos de 7? porque basado en el valor de c, el n0 cambiará.
Pradeep
@Pradeep: Para 1, tienes razón. Para una explicación más profunda: si lo intentamos O(4), eso haría nuestra ecuación de desigualdad c*4 >= 6n+4, y para cualquiera cque escogiéramos, siempre podríamos encontrar un valor donde todos los valores nanteriores hicieran falsa la desigualdad.
Briguy37
@Pradeep: para 2, los valores reales de cy n0no son importantes. Lo que ES importante es que n0existe para los cque elegimos. Para que esto sea cierto, el lado izquierdo de la desigualdad debe aumentar más rápido que el lado derecho para valores grandes de n. c=6no es bueno para esto ( 6n >= 6n+4nunca es cierto), así que elegí c=7. Me podría haber elegido la misma facilidad c=10, c=734o c=6.0000001y todavía habría podido ver que había algo de n0que existía para hacer cierta la desigualdad para n >= n0, lo que significa la Gran Oh estamos probando es válido.
Briguy37
Gracias por una explicación clara. Esto es lo que estaba buscando precisamente. Gracias una vez más.
Pradeep
@Pradeep: Me alegro de poder ayudar :)
Briguy37
1

Si tiene una función de rendimiento 6n + 4, la pregunta relevante es "6 ¿qué?". Como preguntaba un comentario: ¿qué representa tu constante? En términos de física, ¿cuáles son las unidades de tu factor constante?

La razón por la cual la notación O () se usa tan ampliamente para describir el rendimiento del algoritmo es que no hay una forma portátil de responder esa pregunta. Los diferentes procesadores tomarán un número diferente de ciclos de reloj y diferentes cantidades de tiempo para realizar el mismo cálculo elemental, o pueden agrupar los cálculos elementales relevantes de manera diferente. Diferentes lenguajes de computadora, o diferentes descripciones formales e informales como pseudocódigo, representarán algoritmos de formas que son difíciles de comparar directamente. Incluso las implementaciones en el mismo lenguaje pueden representar el mismo algoritmo de diferentes maneras: detalles de formato triviales como el número de líneas a un lado, generalmente tendrá una amplia variedad de opciones estructurales arbitrarias para implementar cualquier algoritmo dado.

Míralo de otra manera: usamos "algoritmo" no para describir una implementación particular, sino para describir una clase completa de implementaciones potenciales del mismo procedimiento general. Esta abstracción ignora los detalles de implementación a favor de documentar algo de valor general, y el factor de rendimiento constante es uno de estos detalles.

Dicho esto, las descripciones de algoritmos a menudo van acompañadas de folclore, notas o incluso puntos de referencia reales que describen el rendimiento de las implementaciones reales en el hardware real. Esto le da una idea aproximada de qué tipo de factor constante esperar, pero también debe tomarse con un grano de sal porque el rendimiento real depende de cosas como cuánto trabajo se llevó a la optimización de una implementación determinada. Además, a largo plazo, el rendimiento relativo de algoritmos comparables tiende a variar a medida que cambia la arquitectura de los últimos y mejores procesadores ...

tormenta
fuente