¿Cuál es la diferencia entre límite inferior y límite estricto?

Con la referencia de esta respuesta , ¿qué es Theta (límite estricto)?

Omega es un límite inferior, bastante conocido, el tiempo mínimo que puede tomar un algoritmo. Y sabemos que Big-O es para límite superior, es decir, el tiempo máximo que puede tomar un algoritmo. Pero no tengo ni idea del Theta.

Big O es el límite superior, mientras que Omega es el límite inferior. Theta requiere tanto Big O como Omega, por eso se lo conoce como un límite estrecho (debe ser tanto el límite superior como el inferior).

Por ejemplo, la toma de un algoritmo Omega(n log n)lleva al menos n log ntiempo, pero no tiene límite superior. La toma de un algoritmo Theta(n log n)es mucho más preferencial ya que toma al menos n log n (Omega n log n) y no más de n log n (Big O n log n).

Θ-notación (theta notación) se llama apretado unida porque es más precisa que la notación O y Ω-notación (omega notación).

Si fuera perezoso, podría decir que la búsqueda binaria en una matriz ordenada es O (n ² ), O (n ³ ) y O (2 ⁿ ), y sería técnicamente correcto en todos los casos. Eso es porque la notación O solo especifica un límite superior , y la búsqueda binaria está limitada en el lado alto por todas esas funciones, pero no muy de cerca. Estas estimaciones perezosas serían inútiles .

La notación Θ resuelve este problema al combinar la notación O y la notación Ω. Si digo que la búsqueda binaria es Θ (log n), eso le da información más precisa. Le dice que el algoritmo está limitado en ambos lados por la función dada, por lo que nunca será significativamente más rápido o más lento de lo indicado.

Si tiene algo que es O (f (n)), eso significa que hay k , g (n) tales que f (n) ≤ kg (n) .

Si tiene algo que es Ω (f (n)), eso significa que hay k , g (n) tales que f (n) ≥ kg (n) .

Y si tienes algo con O (f (n)) y Ω (f (n)) , entonces es Θ (f (n) .

El artículo de Wikipedia es decente, aunque un poco denso.

El límite superior asintótico significa que un algoritmo dado se ejecuta durante la cantidad máxima de tiempo, dependiendo del número de entradas.

Tomemos un algoritmo de clasificación como ejemplo. Si todos los elementos de una matriz están en orden descendente, ordenarlos llevará un tiempo de ejecución de O(n), mostrando la complejidad del límite superior. Si la matriz ya está ordenada, el valor será O(1).

Generalmente, O-notationse utiliza para la complejidad del límite superior.

El límite asintóticamente ajustado (c ₁ g (n) ≤ f (n) ≤ c ₂ g (n)) muestra la complejidad del límite promedio para una función, que tiene un valor entre los límites del límite (límite superior y límite inferior), donde c ₁ y c ₂ son constantes.

Las frases tiempo mínimo y tiempo máximo son un poco engañosas aquí. Cuando hablamos de notaciones O grandes, no es el tiempo real lo que nos interesa, es cómo aumenta el tiempo cuando nuestro tamaño de entrada aumenta. Y generalmente es el tiempo promedio o en el peor de los casos del que estamos hablando, no en el mejor de los casos , que generalmente no es significativo para resolver nuestros problemas.

Usando la búsqueda de matriz en la respuesta aceptada a la otra pregunta como ejemplo. El tiempo que se tarda en encontrar un número particular en la lista de tamaño n es n / 2 * alguna_constante en promedio. Si lo trata como una función f(n) = n/2*some_constant, no aumenta más rápido que g(n) = n, en el sentido dado por Charlie. Además, aumenta no más lento que g(n)ninguno de los dos. Por lo tanto, g(n)es en realidad un límite superior y un límite inferior de f(n)en notación Big-O, por lo que la complejidad de la búsqueda lineal es exactamente n , lo que significa que es Theta (n).

En este sentido, la explicación en la respuesta aceptada a la otra pregunta no es del todo correcta, que afirma que O (n) es un límite superior porque el algoritmo puede ejecutarse en tiempo constante para algunas entradas (este es el mejor caso que mencioné anteriormente, que no es realmente lo que queremos saber sobre el tiempo de ejecución).

Si fuera perezoso, podría decir que la búsqueda binaria en una matriz ordenada es O (n2), O (n3) y O (2n), y sería técnicamente correcto en todos los casos.

Podemos usar la notación o ("pequeño-oh") para denotar un límite superior que no es asintóticamente apretado. Tanto el gran oh como el pequeño oh son similares. Pero, es probable que big-oh se use para definir el límite superior asintóticamente ajustado.

Precisamente el límite inferior o $ \ omega $ bfon f (n) significa el conjunto de funciones que son asintóticamente menores o iguales af (n) es decir, U g (n) ≤ cf (n) $ \ para todo $ `un≥ n 'Para algunos c, n' $ \ en $ $ \ Bbb {N} $

Y el límite superior o $ \ mathit {O} $ en f (n) significa el conjunto de funciones que son asintóticamente mayores o iguales af (n) que matemáticamente dice,

$ g (n) \ ge cf (n) \ para todos los n \ ge n '$, para algunos c, n' $ \ en $ $ \ Bbb {N} $.

Ahora el $ \ Theta $ es la intersección de los dos escritos arriba

$\theta $

Como si un algoritmo fuera como "exactamente $ \ Omega \ left (f (n) \ right $", entonces es mejor decir que es $ \ Theta \ left (f (n) \ right) $.

O también podemos decir que nos da la velocidad real donde $ \omega $nos da el límite más bajo.

La diferencia básica entre

Blockquote

Límite superior asintóticamente y límite superior asintóticamente apretado Asym.upperbound significa un algoritmo dado que puede ejecutarse con una cantidad máxima de tiempo dependiendo del número de entradas, por ejemplo, en el algoritmo de clasificación si todos los elementos de la matriz (n) están en orden descendente y luego para ascenderlos tomará un tiempo de ejecución de O (n) que muestra la complejidad del límite superior, pero si ya están ordenados, tomará ohm (1). Por lo tanto, generalmente usamos la notación "O" para la complejidad del límite superior.

Asym. El límite ajustado muestra el para, por ejemplo, (c1g (n) <= f (n) <= c2g (n)) muestra el límite ajustado de manera que la función tiene el valor entre dos límites (límite superior y límite inferior), dando el caso medio.