big-o - reales - limite superior e inferior excel
Diferencia entre límite inferior y límite apretado? (7)
Si fuera flojo, 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 ("little-oh") para denotar un límite superior que no es asintóticamente ajustado. Tanto big-oh como little-oh son similares. Pero, es probable que big-oh se use para definir un límite superior asintóticamente ajustado.
Con la referencia de esta answer , ¿qué es Theta (límite apretado)?
Omega tiene un límite inferior, bastante conocido, el tiempo mínimo que un algoritmo puede tomar. Y sabemos que Big-O está por límite superior, significa el tiempo máximo que un algoritmo puede tomar. Pero no tengo idea con respecto a Theta.
La diferencia básica entre
Blockquote
asintóticamente límite superior y asintóticamente apretado Asym.upperbound significa un algoritmo dado que puede ejecutarse con el máximo de tiempo dependiendo del número de entradas, por ejemplo, al ordenar algo 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 clasificados, tomará ohm (1). por lo que generalmente usamos la notación "O" para la complejidad del límite superior.
Asym. tightbound bound muestra el por ej. (c1g (n) <= f (n) <= c2g (n)) muestra el límite de límite apretado tal que la función tiene el valor entre dos límites (límite superior e inferior), dando el caso promedio
Las frases tiempo mínimo y tiempo máximo son un poco engañosas aquí. Cuando hablamos de grandes anotaciones en O, no es el momento real en el que estamos interesados, sino cómo aumenta el tiempo cuando aumenta nuestro tamaño de entrada. Y generalmente es el tiempo medio o peor de los casos del que estamos hablando, no 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 un ejemplo. El tiempo que lleva encontrar un número particular en la lista de tamaño n es n / 2 * algo_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, tampoco aumenta más lento que g(n) . Por lo tanto, g(n) es realmente 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 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 tiene algo que es O (f (n)) eso significa que hay k , g (n) tal que f (n) ≤ kg (n) .
Si tiene algo que es Ω (f (n)) eso significa que hay k , g (n) tal que f (n) ≥ kg (n) .
Y si tiene algo con O (f (n)) y Ω (f (n)) , entonces es Θ (f (n) .
El artículo de Wikipedia es decente, aunque un poco denso.
Big O es el límite superior, mientras que Omega es el límite inferior. Theta requiere tanto Big O como Omega, por eso es referido como un límite apretado (debe ser tanto el límite superior como el inferior).
Por ejemplo, un algoritmo que toma Omega(n log n) tarda al menos n log n time, pero no tiene límite superior. Un algoritmo que toma Theta(n log n) es muy preferencial ya que toma al menos n log n (Omega n log n) y no más que n log n (Big O n log n).
La notación (( notación theta) se llama tight-bound porque es más precisa que O-notación y Ω-notación (notación omega).
Si fuera flojo, podría decir que la búsqueda binaria en una matriz ordenada es O (n 2 ), O (n 3 ) y O (2 n ), y sería técnicamente correcto en todos los casos. Esto se debe a que 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 sol resuelve este problema combinando 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. Te 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.
Límite superior asintótico significa que un algoritmo determinado 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, entonces para ordenarlos, tomará 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-notation se usa para la complejidad del límite superior.
Límite asintóticamente estrecho (c 1 g (n) ≤ f (n) ≤ c 2 g (n)) muestra la complejidad promedio unida para una función, que tiene un valor entre límites (límite superior e inferior), donde c 1 y c 2 son constantes.