algorithm - explicacion - notacion de un algoritmo

Diferencia entre la notación Big-Theta y Big O en lenguaje simple

Question

Mientras trataba de entender la diferencia entre la notación Theta y O , encontré la siguiente afirmación:

The Theta-notation asymptotically bounds a function from above and below. When
we have only an asymptotic upper bound, we use O-notation.

Pero no entiendo esto. El libro lo explica matemáticamente, pero es demasiado complejo y se vuelve realmente aburrido de leer cuando realmente no entiendo.

¿Alguien puede explicar la diferencia entre los dos utilizando ejemplos simples pero poderosos ?

Answer 1

Aquí está mi intento:

Una función, f(n) es O(n) , si y solo si existe una constante, c , tal que f(n) <= c*g(n) .

Usando esta definición, ¿podríamos decir que la función f(2^(n+1)) es O(2^n) ?

1. En otras palabras, ¿existe una constante ''c'' tal que 2^(n+1) <= c*(2^n) ? Tenga en cuenta que la segunda función ( 2^n ) es la función después de Big O en el problema anterior. Esto me confundió al principio.

2. Entonces, usa tus habilidades básicas de álgebra para simplificar esa ecuación. 2^(n+1) se descompone en 2 * 2^n . Al hacerlo, nos quedamos con:

   2 * 2^n <= c(2^n)

3. Ahora es fácil, la ecuación se mantiene para cualquier valor de c donde c >= 2 . Entonces, sí, podemos decir que f(2^(n+1)) es O(2^n) .

Big Omega funciona de la misma manera, excepto que evalúa f(n) > = c*g(n) para alguna constante ''c'' .

Entonces, al simplificar las funciones anteriores de la misma manera, nos quedamos con (note el> = ahora):

2 * 2^n >= c(2^n)

Entonces, la ecuación funciona para el rango 0 <= c <= 2 . Entonces, podemos decir que f(2^(n+1)) es Big Omega de (2^n) .

Ahora, ya que AMBOS de los que se mantienen, podemos decir que la función es Big Theta ( 2^n ). Si uno de ellos no trabajaría para una constante de ''c'' , entonces no es Big Theta.

El ejemplo anterior fue tomado del Manual de diseño de algoritmos de Skiena, que es un libro fantástico.

Espero que ayude. Este es realmente un concepto difícil de simplificar. No te obsesiones tanto con lo que es ''c'' , simplemente divídelo en términos más simples y usa tus habilidades básicas de álgebra.

Answer 2

Big O solo proporciona un límite superior asintótico, mientras que Big Theta también proporciona un límite inferior.

Todo lo que es Theta(f(n)) también es O(f(n)) , pero no al revés.
Se dice que T(n) es Theta(f(n)) , si es tanto O(f(n)) como Omega(f(n))

Por esta razón, la gran Theta es más informativa que la notación de la gran O , por lo que si podemos decir que algo es la gran Theta, generalmente se prefiere. Sin embargo, es más difícil probar que algo es Theta grande, que probar que es big-O.

Por ejemplo , la ordenación de mezcla es O(n*log(n)) y Theta(n*log(n)) , pero también es O (n ² ), ya que n ² es asintóticamente "más grande" que él. Sin embargo, NO es Theta (n ² ), ya que el algoritmo NO es Omega (n ² ).

Omega(n) es el límite inferior asintótico . Si T(n) es Omega(f(n)) , significa que a partir de cierto n0 , hay una constante C1 tal que T(n) >= C1 * f(n) . Mientras que big-O dice que hay una constante C2 tal que T(n) <= C2 * f(n)) .

Los tres (Omega, O, Theta) dan solo información asintótica ("para grandes aportes"):

• Big O da límite superior
• Big Omega da límite inferior y
• Big Theta da ambos límites inferiores y superiores

Tenga en cuenta que esta notación no está relacionada con los mejores, peores y análisis de casos promedio de algoritmos. Cada uno de estos puede ser aplicado a cada análisis.

Answer 3

Citaré el volumen 1 de TAOCP de Knuth - página 110 (tengo la edición india). Recomiendo leer las páginas 107-110 ( sección 1.2.11 Representaciones asintóticas )

La gente a menudo confunde la O-notación suponiendo que da un orden exacto de Crecimiento; lo usan como si especificara un límite inferior así como un límite superior. Por ejemplo, un algoritmo podría llamarse ineficiente porque su tiempo de ejecución es O (n ^ 2). Pero un tiempo de ejecución de O (n ^ 2) no significa necesariamente que el tiempo de ejecución no sea también O (n)

En la página 107,

1 ^ 2 + 2 ^ 2 + 3 ^ 2 + ... + n ^ 2 = O (n ^ 4) y

1 ^ 2 + 2 ^ 2 + 3 ^ 2 + ... + n ^ 2 = O (n ^ 3) y

1 ^ 2 + 2 ^ 2 + 3 ^ 2 + ... + n ^ 2 = (1/3) n ^ 3 + O (n ^ 2)

Big-Oh es para aproximaciones. Te permite reemplazar ~ con un signo igual =. En el ejemplo anterior, para n muy grandes, podemos estar seguros de que la cantidad se mantendrá por debajo de n ^ 4 y n ^ 3 y (1/3) n ^ 3 + n ^ 2 [y no simplemente n ^ 2]

Big Omega es para límites inferiores: un algoritmo con Omega (n ^ 2) no será tan eficiente como uno con O (N logN) para N grande. Sin embargo, no sabemos a qué valores de N (en ese sentido sabemos) aproximadamente)

Big Theta es para el orden exacto de crecimiento, tanto en el límite inferior como en el superior.

Answer 4

Si el tiempo de ejecución se expresa en notación de gran O, sabes que el tiempo de ejecución no será más lento que la expresión dada. Expresa el peor de los casos.

Pero con la notación Theta también sabías que no será más rápido. Es decir, no hay un mejor escenario para que el algoritmo vuelva a funcionar más rápido.

Esto da un límite más exacto en el tiempo de ejecución esperado. Sin embargo, para la mayoría de los propósitos, es más simple ignorar el límite inferior (la posibilidad de una ejecución más rápida), mientras que en general solo le preocupa el peor escenario.

Answer 5

Voy a usar un ejemplo para ilustrar la diferencia.

Que la función f (n) se defina como

if n is odd f(n) = n^3
if n is even f(n) = n^2

De CLRS

Una función f (n) pertenece al conjunto Θ (g (n)) si existen constantes positivas c1 y c2, de manera que se puede "intercalar" entre c1g (n) y c2g (n), para n lo suficientemente grande.

Y

O (g (n)) = {f (n): existen constantes positivas c y n0, de modo que 0 ≤ f (n) ≤ cg (n) para todos n ≥ n0}.

Y

Ω (g (n)) = {f (n): existen constantes positivas c y n0, de modo que 0 ≤ cg (n) ≤ f (n) para todos n ≥ n0}.

El límite superior en f (n) es n ^ 3. Entonces nuestra función f (n) es claramente O (n ^ 3).

¿Pero es Θ (n ^ 3)?

Para que f (n) esté en Θ (n ^ 3), debe estar intercalado entre dos funciones, una que forma el límite inferior y la otra el límite superior, ambas crecidas en n ^ 3. Mientras que el límite superior es obvio, el límite inferior no puede ser n ^ 3. El límite inferior es de hecho n ^ 2; f (n) es Ω (n ^ 2)

De CLRS

Para cualquiera de las dos funciones f (n) yg (n), tenemos f (n) = Θ (g (n)) si y solo si f (n) = O (g (n)) yf (n) = Ω (g (n)).

Por lo tanto, f (n) no está en Θ (n ^ 3) mientras que está en O (n ^ 3) y Ω (n ^ 2)