sheet rapper little for exercises examples dummies cheat big big-o time-complexity notation big-theta

big o - rapper - ¿Cuál es la diferencia entre Θ(n) y O(n)?



big o rapper (9)

A veces veo Θ (n) con el extraño Θ símbolo con algo en medio, y otras veces solo O (n). ¿Es solo la pereza de escribir porque nadie sabe cómo escribir este símbolo, o significa algo diferente?

Conclusión: consideramos big O, big θ y big Ω como la misma cosa.

¿Por qué? Te diré la razón a continuación:

En primer lugar, aclararé una afirmación errónea, algunas personas piensan que solo nos importa la peor complejidad de tiempo, por lo que siempre usamos big O en lugar de big θ. Diré que este hombre es una tontería. Los límites superior e inferior se usan para describir una función, no para describir la complejidad del tiempo. La peor función de tiempo tiene su límite superior e inferior; La mejor función de tiempo tiene su límite superior e inferior también.

Para explicar claramente la relación entre la gran O y la gran, explicaré primero la relación entre la gran O y la pequeña o. De la definición, podemos saber fácilmente que la pequeña o es un subconjunto de la gran O. Por ejemplo:

T (n) = n ^ 2 + n, podemos decir T (n) = O (n ^ 2), T (n) = O (n ^ 3), T (n) = O (n ^ 4). Pero para pequeña o, T (n) = o (n ^ 2) no cumple con la definición de pequeña o. Así que solo T (n) = o (n ^ 3), T (n) = o (n ^ 4) son correctos para una pequeña o. ¿El redundante T (n) = O (n ^ 2) es qué? Es grande θ!

En general, decimos que O grande es O (n ^ 2), difícilmente decir T (n) = O (n ^ 3), T (n) = O (n ^ 4). ¿Por qué? Porque consideramos la gran O como la gran θ subconscientemente.

Del mismo modo, también consideramos que el gran Ω es grande θ subconscientemente.

En una palabra, gran O, gran θ y grande Ω no son lo mismo de las definiciones, pero son lo mismo en nuestra boca y cerebro.

Usando limites

Consideremos f(n) > 0 y g(n) > 0 para todos n . Está bien considerar esto, porque el algoritmo real más rápido tiene al menos una operación y completa su ejecución después del inicio. Esto simplificará el cálculo, porque podemos usar el valor ( f(n) ) en lugar del valor absoluto ( |f(n)| ).

  1. f(n) = O(g(n))

    General:

    f(n) 0 ≤ lim ──────── < ∞ n➜∞ g(n)

    Para g(n) = n :

    f(n) 0 ≤ lim ──────── < ∞ n➜∞ n

    Ejemplos:

    Expression Value of the limit ------------------------------------------------ n = O(n) 1 1/2*n = O(n) 1/2 2*n = O(n) 2 n+log(n) = O(n) 1 n = O(n*log(n)) 0 n = O(n²) 0 n = O(nⁿ) 0

    Contraejemplos:

    Expression Value of the limit ------------------------------------------------- n ≠ O(log(n)) ∞ 1/2*n ≠ O(sqrt(n)) ∞ 2*n ≠ O(1) ∞ n+log(n) ≠ O(log(n)) ∞

  2. f(n) = Θ(g(n))

    General:

    f(n) 0 < lim ──────── < ∞ n➜∞ g(n)

    Para g(n) = n :

    f(n) 0 < lim ──────── < ∞ n➜∞ n

    Ejemplos:

    Expression Value of the limit ------------------------------------------------ n = Θ(n) 1 1/2*n = Θ(n) 1/2 2*n = Θ(n) 2 n+log(n) = Θ(n) 1

    Contraejemplos:

    Expression Value of the limit ------------------------------------------------- n ≠ Θ(log(n)) ∞ 1/2*n ≠ Θ(sqrt(n)) ∞ 2*n ≠ Θ(1) ∞ n+log(n) ≠ Θ(log(n)) ∞ n ≠ Θ(n*log(n)) 0 n ≠ Θ(n²) 0 n ≠ Θ(nⁿ) 0

Breve explicación:

Si un algoritmo es de Θ (g (n)), significa que el tiempo de ejecución del algoritmo a medida que n (tamaño de entrada) aumenta es proporcional a g (n).

Si un algoritmo es de O (g (n)), significa que el tiempo de ejecución del algoritmo a medida que n aumenta es a lo sumo proporcional a g (n).

Normalmente, incluso cuando las personas hablan de O (g (n)) en realidad significan Θ (g (n)) pero técnicamente, hay una diferencia.

Más técnicamente:

O (n) representa el límite superior. Θ (n) significa enlace apretado. Ω (n) representa el límite inferior.

f (x) = Θ (g (x)) iff f (x) = O (g (x)) yf (x) = Ω (g (x))

Básicamente, cuando decimos que un algoritmo es de O (n), también es O (n 2 ), O (n 1000000 ), O (2 n ), ... pero un algoritmo Θ (n) no es Θ (n 2 ) .

De hecho, como f (n) = Θ (g (n)) significa que para valores suficientemente grandes de n, f (n) se puede unir dentro de c 1 g (n) y c 2 g (n) para algunos valores de c 1 y c 2 , es decir, la tasa de crecimiento de f es asintóticamente igual a g: g puede ser un límite inferior y un límite superior de f. Esto implica directamente que f puede ser un límite inferior y también un límite superior de g. Por consiguiente,

f (x) = Θ (g (x)) iff g (x) = Θ (f (x))

De manera similar, para mostrar f (n) = Θ (g (n)), basta con mostrar que g es un límite superior de f (es decir, f (n) = O (g (n))) yf es un límite inferior de g (es decir, f (n) = Ω (g (n)) que es exactamente lo mismo que g (n) = O (f (n))). Concisamente

f (x) = Θ (g (x)) iff f (x) = O (g (x)) y g (x) = O (f (x))

También hay notaciones little-oh y little-omega ( ω ) que representan los límites superior e inferior sueltos de una función.

Para resumir:

f(x) = O(g(x)) (big-oh) significa que la tasa de crecimiento de f(x) es asintóticamente menor o igual que la tasa de crecimiento de g(x) .

f(x) = Ω(g(x)) (big-omega) significa que la tasa de crecimiento de f(x) es asintóticamente mayor o igual que la tasa de crecimiento de g(x)

f(x) = o(g(x)) (poco-oh) significa que la tasa de crecimiento de f(x) es asintóticamente menor que la tasa de crecimiento de g(x) .

f(x) = ω(g(x)) (little-omega) significa que la tasa de crecimiento de f(x) es asintóticamente mayor que la tasa de crecimiento de g(x)

f(x) = Θ(g(x)) (theta) significa que la tasa de crecimiento de f(x) es asintóticamente igual a la tasa de crecimiento de g(x)

Para una discusión más detallada, puede leer la definición en Wikipedia o consultar un libro de texto clásico como Introduction to Algorithms por Cormen et al.

En lugar de proporcionar una definición teórica, que ya está muy bien resumida aquí, daré un ejemplo simple:

Suponga que el tiempo de ejecución de f(i) es O(1) . A continuación se muestra un fragmento de código cuyo tiempo de ejecución asintótico es Θ(n) . Siempre llama a la función f(...) n veces. Tanto el límite inferior como el superior es n.

for(int i=0; i<n; i++){ f(i); }

El segundo fragmento de código a continuación tiene el tiempo de ejecución asintótico de O(n) . Llama a la función f(...) como máximo n veces. El límite superior es n, pero el límite inferior podría ser Ω(1) o Ω(log(n)) , dependiendo de lo que ocurra dentro de f2(i) .

for(int i=0; i<n; i++){ if( f2(i) ) break; f(i); }

Hay una forma simple (un truco, supongo) de recordar qué notación significa qué.

Se puede considerar que todas las notaciones Big-O tienen una barra.

Cuando se mira un, la barra está en la parte inferior, por lo que es un límite inferior (asintótico).

Cuando se mira un, la barra está obviamente en el medio. Así que es un enlace apretado (asintótico).

Cuando escribe la letra O, normalmente termina en la parte superior y dibuja un garabato. Por lo tanto, O (n) es el límite superior de la función. Para ser justos, este no funciona con la mayoría de las fuentes, pero es la justificación original de los nombres.

Theta es una forma abreviada de referirse a una situación especial en la que la O grande y la Omega son iguales.

Por lo tanto, si uno afirma que The Theta is expression q , entonces también necesariamente afirman que Big O is expression q y Omega is expression q .

Analogía aproximada:

Si: Theta afirma: "Ese animal tiene 5 patas". luego se deduce que: Big O es verdadero ("Ese animal tiene menos o igual a 5 patas") y Omega es verdadero ("Ese animal tiene más o igual que 5 patas").

Es solo una analogía aproximada porque las expresiones no son necesariamente números específicos, sino que tienen funciones de diferentes órdenes de magnitud, como log (n), n, n ^ 2, (etc.).

Un chart podría hacer que las respuestas anteriores sean más fáciles de entender:

Θ-Notación - Mismo orden | O-notación - límite superior

En inglés,

A la izquierda, observe que hay un límite superior y un límite inferior que son del mismo orden de magnitud (es decir, g (n) ). Ignore las constantes, y si el límite superior y el límite inferior tienen el mismo orden de magnitud, se puede decir válidamente que f (n) = Θ (g (n)) o f (n) está en theta grande de g (n) .

Comenzando con la derecha, el ejemplo más simple es decir que el límite superior g (n) es simplemente el orden de magnitud e ignora la constante c (como lo hace toda notación O grande ).

uno es grande "O"

uno es Big Theta

http://en.wikipedia.org/wiki/Big_O_notation

Big O significa que su algoritmo se ejecutará en no más pasos que en la expresión dada (n ^ 2)

Big Omega significa que su algoritmo se ejecutará en no menos pasos que en la expresión dada (n ^ 2)

Cuando ambas condiciones son verdaderas para la misma expresión, puedes usar la notación theta grande ...