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?
big-o
algorithm-analysis
Pradeep
fuente
fuente
Respuestas:
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.
fuente
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.
fuente
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'}
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
".fuente
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,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.fuente
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 - 5000
o5000 n + 60000
? Porn
menos 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).
fuente
(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:
Primero, seamos
O(g(n))
la notación Big Oh que estamos tratando de encontrarf(n)
. A partir de la definición de Big Oh, necesitamos encontrar un simplificadog(n)
donde existan algunas constantesc
yn0
dondec*g(n) >= f(n)
sea cierto para todosn
los mayores quen0
.Primero, elijamos
g(n) = 6n + 4
(lo que daría lugarO(6n+4)
en Big Oh). En este caso, vemos quec = 1
y cualquier valor den0
cumplirá con los requisitos matemáticos de nuestra definición de Big Oh, ya queg(n)
siempre es igual af(n)
:En este punto, hemos cumplido los requisitos matemáticos. Si nos detenemos
O(6n+4)
, está claro que esto no es más útil que escribirf(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
6n
modo que el Big Oh esO(4)
? ¡No! (Ejercicio para el lector si no entiende por qué)En segundo lugar, ¿podemos simplificar
4
para que el Big Oh seaO(6n)
? ¡Si! En ese casog(n) = 6n
, entonces:En este punto, elijamos
c = 2
desde entonces que el lado izquierdo aumentará más rápido (en 12) que el lado derecho (en 6) para cada incremento den
.Ahora necesitamos encontrar un punto positivo
n0
donde la ecuación anterior sea verdadera para todosn
los 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 quen0 = 2
hace que lo anterior sea cierto, lo sabemosg(n)=6n
oO(6n)
es una notación potencial de Big Ohf(n)
.Ahora, ¿podemos simplificar
6
para que el Big Oh seaO(n)
? ¡Si! En ese casog(n) = n
, entonces:Vamos a elegir
c = 7
ya que la izquierda aumentaría más rápido que la derecha.Vemos que lo anterior será cierto para todos
n
los mayores o iguales an0 = 4
. Por lo tanto,O(n)
es una notación potencial para Big Ohf(n)
. ¿Podemos simplificarg(n)
más? No!Finalmente, hemos descubierto que la notación Big Oh más simple
f(n)
esO(n)
. ¿Por qué pasamos por todo esto? Porque ahora sabemos quef(n)
es lineal , ya que su notación Big Oh es de complejidad linealO(n)
. ¡Lo bueno es que ahora podemos comparar la complejidad temporal def(n)
otros algoritmos! Por ejemplo, ahora sabemos quef(n)
es comparable de tiempo-complejidad de las funcionesh(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 tiempoO(n)
.¡¡¡Dulce!!!
fuente
O(4)
, eso haría nuestra ecuación de desigualdadc*4 >= 6n+4
, y para cualquierac
que escogiéramos, siempre podríamos encontrar un valor donde todos los valoresn
anteriores hicieran falsa la desigualdad.c
yn0
no son importantes. Lo que ES importante es quen0
existe para losc
que 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 den
.c=6
no es bueno para esto (6n >= 6n+4
nunca es cierto), así que elegíc=7
. Me podría haber elegido la misma facilidadc=10
,c=734
oc=6.0000001
y todavía habría podido ver que había algo den0
que existía para hacer cierta la desigualdad paran >= n0
, lo que significa la Gran Oh estamos probando es válido.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 ...
fuente