algorithm - minuscula - notacion pequeña o grande omega y gran theta

¿Qué representa exactamente la notación grande Ө? (4)

Estoy realmente confundido acerca de las diferencias entre el gran O, el gran Omega y la gran notación Theta.

Entiendo que el gran O es el límite superior y el gran Omega es el límite inferior, pero ¿qué representa exactamente el gran Ө (theta)?

He leído que significa apretado , pero ¿qué significa eso?

Para responder a su pregunta, la notación asintótica y las Funciones en notación asintótica también deben explicarse. Si tienes paciencia para leerlo todo, las cosas serán muy claras al final.

1. Notación asintótica

Para pensar en algoritmos puedes usar 2 ideas principales:

Determine cuánto tiempo tarda el algoritmo en términos de su entrada.
Céntrese en qué tan rápido crece una función con el tamaño de entrada; aka tasa de crecimiento del tiempo de ejecución. Ejemplo: supongamos que un algoritmo, ejecutándose en una entrada de tamaño n, toma instrucciones de la máquina 6n ^ 2 + 100n + 300. El término 6n ^ 2 se vuelve más grande que los términos restantes, 100 n + 300, una vez que n llega a ser lo suficientemente grande, 20 en este caso.

Diríamos que el tiempo de ejecución de este algoritmo crece como n ^ 2, dejando caer el coeficiente 6 y los términos restantes 100n + 300. Realmente no importa qué coeficientes usemos; siempre que el tiempo de ejecución sea n ^ 2 + b n + c, para algunos números a> 0, b y c, siempre habrá un valor de n para el cual a n ^ 2 es mayor que b n + c , y esta diferencia aumenta a medida que n aumenta. Al eliminar los coeficientes constantes y los términos menos significativos, utilizamos la notación asintótica.

2. Big-Theta

Aquí hay una implementación simple de búsqueda lineal

var doLinearSearch = function(array) { for (var guess = 0; guess < array.length; guess++) { if (array[guess] === targetValue) { return guess; // found it! } } return -1; // didn''t find it };

Cada uno de estos pequeños cálculos requiere una cantidad constante de tiempo cada vez que se ejecuta. Si for-loop itera n veces, entonces el tiempo para todas las n iteraciones es c1 * n, donde c 1 es la suma de los tiempos para los cálculos en una iteración de bucle. Este código tiene un poco de sobrecarga adicional, para configurar el for-loop (incluida la inicialización de adivinar a 0) y posiblemente devolver -1 al final. Llamemos a la hora de este overhead c 2, que también es una constante. Por lo tanto, el tiempo total para la búsqueda lineal en el peor de los casos es c 1 * n + c 2.
el factor constante c 1 y el término de bajo orden c 2 no nos dicen acerca de la tasa de crecimiento del tiempo de ejecución. Lo que es significativo es que el peor tiempo de ejecución de búsqueda lineal crece como el tamaño de matriz n. La notación que usamos para este tiempo de ejecución es Θ (n). Esa es la letra griega "theta", y decimos "big-Theta of n" o simplemente "Theta of n".
Cuando decimos que un tiempo de ejecución particular es Θ (n), estamos diciendo que una vez que n es lo suficientemente grande, el tiempo de ejecución es al menos k 1 * ny a lo sumo k 2 * n para algunos constantes k 1 y k 2. He aquí cómo pensar en Θ (n)
Para valores pequeños de n, no nos importa cómo el tiempo de ejecución se compara con k 1 * n o k 2 * n. Pero una vez que n se pone lo suficientemente grande, ya sea a la derecha de la línea punteada, el tiempo de ejecución debe estar intercalado entre k 1 * nyk 2 * n. Mientras existan estas constantes k 1 y k 2, decimos que el tiempo de ejecución es Θ (n).
Cuando usamos la notación big-,, estamos diciendo que tenemos un límite asintóticamente estrecho en el tiempo de ejecución. "Asintóticamente" porque solo importa valores grandes de n. "Ajustado" porque hemos calculado el tiempo de ejecución dentro de un factor constante arriba y abajo.

3. Funciones en notación asintótica

Supongamos que un algoritmo tomara una cantidad de tiempo constante, independientemente del tamaño de la entrada. Por ejemplo, si te dieran una matriz que ya está ordenada en orden creciente y tuvieras que encontrar el elemento mínimo, llevaría un tiempo constante, ya que el elemento mínimo debe estar en el índice 0. Dado que nos gusta usar una función de n en notación asintótica, se podría decir que este algoritmo se ejecuta en Θ (n ^ 0) tiempo. ¿Por qué? Porque n ^ 0 = 1, y el tiempo de ejecución del algoritmo está dentro de un factor constante de 1. En la práctica, no escribimos Θ (n ^ 0), sin embargo; escribimos Θ (1)
Aquí hay una lista de funciones en notación asintótica que a menudo encontramos al analizar algoritmos, enumerados desde el crecimiento más lento hasta el más rápido. Esta lista no es exhaustiva; hay muchos algoritmos cuyos tiempos de ejecución no aparecen aquí:
Θ (1) (también conocido como búsqueda constante)
Θ (lg n) (también conocida como búsqueda binaria)
Θ (n) (también conocido como búsqueda lineal)
Θ (n * lg n)
Θ (n ^ 2)
Θ (n ^ 2 * lg n)
Θ (n ^ 3)
Θ (2 ^ n)
Tenga en cuenta que una función exponencial a ^ n, donde a> 1, crece más rápido que cualquier función polinomial n ^ b, donde b es cualquier constante.

4. Notación de Big-O

Usamos la notación big-to para unir de forma asintótica el crecimiento de un tiempo de ejecución dentro de factores constantes arriba y abajo. A veces queremos atacar solo desde arriba. Sería conveniente tener una forma de notación asintótica que significa que "el tiempo de ejecución crece a lo mucho, pero podría crecer más lentamente". Usamos la notación "big-O" para esas ocasiones.
Si el tiempo de ejecución es O (f (n)), entonces para un n suficientemente grande, el tiempo de ejecución es como máximo k * f (n) para alguna constante k. A continuación, le indicamos cómo pensar en un tiempo de ejecución que es O (f (n)):
Si vuelves a la definición de notación big-,, notarás que se parece mucho a la notación de gran O, excepto que la notación de big-bounds limita la ejecución tanto desde arriba como desde abajo, en vez de solo desde arriba. Si decimos que un tiempo de ejecución es Θ (f (n)) en una situación particular, entonces también es O (f (n)). Por ejemplo, podemos decir que debido a que el peor tiempo de ejecución de búsqueda binaria es Θ (lg n), también es O (lg n). Lo contrario no es necesariamente cierto: como hemos visto, podemos decir que la búsqueda binaria siempre se ejecuta en el tiempo O (lg n), pero no que siempre se ejecute en Θ (lg n) tiempo.
Supongamos que tiene 10 dólares en su bolsillo. Acude a tu amigo y dices: "Tengo una cantidad de dinero en el bolsillo y te garantizo que no será más de un millón de dólares". Su declaración es absolutamente cierta, aunque no terriblemente precisa. Un millón de dólares es un límite superior de 10 dólares, al igual que O (n) es un límite superior en el tiempo de ejecución de la búsqueda binaria.
Otros límites superiores imprecisos en la búsqueda binaria serían O (n ^ 2), O (n ^ 3) y O (2 ^ n). Pero ninguno de Θ (n), Θ (n ^ 2), Θ (n ^ 3), andΘ (2 ^ n) sería correcto para describir el tiempo de ejecución de la búsqueda binaria en cualquier caso.

5. Notación Big-Ω (Big-Omega)

A veces, queremos decir que un algoritmo toma al menos una cierta cantidad de tiempo, sin proporcionar un límite superior. Usamos la notación big-Ω; esa es la letra griega "omega".
Si el tiempo de ejecución es Ω (f (n)), entonces para un n suficientemente grande, el tiempo de ejecución es al menos k * f (n) para alguna constante k. A continuación, le mostramos cómo pensar en un tiempo de ejecución que es Ω (f (n)):
Decimos que el tiempo de ejecución es "grande-Ω de f (n)". Usamos la notación big-Ω para los límites inferiores asintóticos, ya que limita el crecimiento del tiempo de ejecución desde abajo para tamaños de entrada lo suficientemente grandes.
Así como Θ (f (n)) implica automáticamente O (f (n)), también implica automáticamente Ω (f (n)). Entonces, podemos decir que el peor tiempo de ejecución de la búsqueda binaria es Ω (lg n). También podemos hacer afirmaciones correctas, pero imprecisas, usando notación de big-Ω. Por ejemplo, como si realmente tuvieras un millón de dólares en tu bolsillo, puedes decir con sinceridad "Tengo una cantidad de dinero en el bolsillo, y son al menos 10 dólares", también puedes decir que se está ejecutando el peor de los casos el tiempo de búsqueda binaria es Ω (1), ya que lleva al menos un tiempo constante.

Referencia: https://www.khanacademy.org

Primero, comprendamos lo que son la gran O, la gran Theta y la gran Omega. Son todos sets de funciones.

Big O está dando límite superior asintótico , mientras que el gran Omega está dando un límite inferior. Big Theta da los dos.

Todo lo que es Ө(f(n)) también es O(f(n)) , pero no al revés.
Se dice que T(n) está en Ө(f(n)) si está tanto en O(f(n)) como en Omega(f(n)) .
En la terminología de conjuntos, Ө(f(n)) es la intersection de O(f(n)) y Omega(f(n))

Por ejemplo, el peor caso de combinación es O(n*log(n)) y Omega(n*log(n)) - y también es Ө(n*log(n)) , pero también es O(n^2) , ya que n^2 es asintóticamente "más grande" que él. Sin embargo, no es Ө(n^2) , ya que el algoritmo no es Omega(n^2) .

Una explicación matemática un poco más profunda

O(n) es un límite superior asintótico. Si T(n) es O(f(n)) , significa que a partir de cierto n0 , hay una constante C tal que T(n) <= C * f(n) . Por otro lado, Big-Omega dice que hay un C2 constante tal que T(n) >= C2 * f(n)) ).

¡No confundir!

No debe confundirse con el peor, el mejor y el promedio de análisis de casos: las tres notación (Omega, O, Theta) no están relacionadas con el mejor, peor y promedio de casos de análisis de algoritmos. Cada uno de estos se puede aplicar a cada análisis.

Usualmente lo usamos para analizar la complejidad de los algoritmos (como el ejemplo de combinación de fusión anterior). Cuando decimos "Algoritmo A es O(f(n)) ", lo que realmente queremos decir es "La complejidad de los algoritmos bajo el peor análisis de un caso es O(f(n)) " - es decir - escala "similar" (o formalmente, no peor que) la función f(n) .

¿Por qué nos preocupamos por el límite asintótico de un algoritmo?

Bueno, hay muchas razones para ello, pero creo que las más importantes son:

Es mucho más difícil determinar la función de complejidad exacta , por lo tanto, "comprometemos" las notaciones de gran O / gran-Theta, que son lo suficientemente informativas teóricamente.
El número exacto de operaciones también depende de la plataforma . Por ejemplo, si tenemos un vector (lista) de 16 números. ¿Cuánto tiempo tomará? La respuesta es, depende. Algunas CPU permiten adiciones de vectores, mientras que otras no, por lo que la respuesta varía entre diferentes implementaciones y máquinas diferentes, que es una propiedad no deseada. Sin embargo, la notación de gran O es mucho más constante entre las máquinas y las implementaciones.

Para demostrar este problema, eche un vistazo a los siguientes gráficos:

Está claro que f(n) = 2*n es "peor" que f(n) = n . Pero la diferencia no es tan drástica como la de la otra función. Podemos ver que f(n)=logn rápidamente obteniendo mucho más bajo que las otras funciones, f(n) = n^2 está obteniendo rápidamente mucho más alto que los otros.
Entonces, debido a las razones anteriores, "ignoramos" los factores constantes (2 * en el ejemplo de gráficos) y tomamos solo la notación de O grande.

En el ejemplo anterior, f(n)=n, f(n)=2*n estarán ambos en O(n) y en Omega(n) y, por lo tanto, también estarán en Theta(n) .
Por otro lado, f(n)=logn estará en O(n) (es "mejor" que f(n)=n ), pero NO estará en Omega(n) , y por lo tanto tampoco estará en Theta(n) .
Simétricamente, f(n)=n^2 estará en Omega(n) , pero NO en O(n) , y por lo tanto - tampoco es Theta(n) .

¹ Usualmente, aunque no siempre. cuando falta la clase de análisis (peor, promedio y mejor), realmente queremos decir el peor de los casos.

Significa que el algoritmo es grande-O y grande-Omega en la función dada.

Por ejemplo, si es Ө(n) , entonces hay una constante k , tal que su función (tiempo de ejecución, lo que sea), es mayor que n*k para n suficientemente grande, y alguna otra constante K tal que su función es más pequeño que n*K para n suficientemente grande.

En otras palabras, para n suficientemente grande, se encuentra entre dos funciones lineales:

Para k < K y n suficientemente grande, n*k < f(n) < n*K

Theta (n): una función f(n) pertenece a Theta(g(n)) , si existen constantes positivas c1 y c2 tales que f(n) puede intercalarse entre c1(g(n)) y c2(g(n)) . es decir, da tanto límite superior como inferior.

Theta (g (n)) = {f (n): existen constantes positivas c1, c2 y n1 tales que 0 <= c1 (g (n)) <= f (n) <= c2 (g (n)) para todo n> = n1}

cuando decimos f(n)=c2(g(n)) o f(n)=c1(g(n)) representa un límite apretado asintóticamente.

O (n): da solo límite superior (puede o no ser ajustado)

O (g (n)) = {f (n): existen constantes positivas c y n1 tales que 0 <= f (n) <= cg (n) para todo n> = n1}

ex : El límite 2*(n^2) = O(n^2) es asintóticamente ajustado, mientras que el límite 2*n = O(n^2) no es asintóticamente ajustado.

o (n): solo da límite superior (nunca un límite estrecho)

la diferencia notable entre O (n) y o (n) es f (n) es menor que cg (n) para todo n> = n1 pero no igual que en O (n).

ex : 2*n = o(n^2) , pero 2*(n^2) != o(n^2)