Ten en cuenta que en la informática un error casi siempre tiene varias soluciones, así que te compartimos lo más óptimo y eficiente.
Solución:
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 crece es a lo sumo proporcional a g(n).
Normalmente, incluso cuando las personas hablan de O(g(n)) en realidad quieren decir Θ(g(n)), pero técnicamente hay una diferencia.
Más técnicamente:
O(n) representa el límite superior. Θ(n) significa límite estrecho. Ω(n) representa el límite inferior.
f(x) = Θ(g(x)) si y solo f(x) = O(g(x)) y f(x) = Ω(g(x))
Básicamente, cuando decimos que un algoritmo es de O(n), también es O(n2), En1000000), O(2norte), … pero un algoritmo Θ(n) es no Θ(n2).
De hecho, dado que f(n) = Θ(g(n)) significa que para valores suficientemente grandes de n, f(n) se puede acotar dentro de c1g(n) yc2g(n) para algunos valores de c1 y C2es decir, la tasa de crecimiento de f es asintóticamente igual a g: g puede ser un límite inferior y 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. Como consecuencia,
f(x) = Θ(g(x)) si y solo g(x) = Θ(f(x))
De manera similar, para mostrar f(n) = Θ(g(n)), es suficiente mostrar que g es un límite superior de f (es decir, f(n) = O(g(n))) y f es un límite inferior de g (es decir, f(n) = Ω(g(n)) que es exactamente lo mismo que g(n) = O(f(n))). de manera concisa,
f(x) = Θ(g(x)) si y sólo si f(x) = O(g(x)) y g(x) = O(f(x))
También hay little-oh y little-omega (ω) notaciones que representan límites sueltos superior e inferior sueltos de una función.
Para resumir:
f(x) = O(g(x))(gran-oh) significa que la tasa de crecimiento def(x)es asintóticamente Menos que o igual a a la tasa de crecimiento deg(x).
f(x) = Ω(g(x))(gran omega) significa que la tasa de crecimiento def(x)es asintóticamente Mayor qué o igual a la tasa de crecimiento deg(x)
f(x) = o(g(x))(pequeño-oh) significa que la tasa de crecimiento def(x)es asintóticamente menos que la tasa de crecimiento deg(x).
f(x) = ω(g(x))(poco-omega) significa que la tasa de crecimiento def(x)es asintóticamente mas grande que la tasa de crecimiento deg(x)
f(x) = Θ(g(x))(theta) significa que la tasa de crecimiento def(x)es asintóticamente igual a la tasa de crecimiento deg(x)
Para una discusión más detallada, puede leer la definición en Wikipedia o consultar un libro de texto clásico como Introducción a los algoritmos de Cormen et al.
Hay una forma sencilla (un truco, supongo) de recordar qué notación significa qué.
Se puede considerar que todas las notaciones Big-O tienen una barra.
Al mirar un Ω, la barra está en la parte inferior, por lo que es un límite inferior (asintótico).
Al mirar un Θ, la barra está obviamente en el medio. Por lo tanto, es un límite estrecho (asintótico).
Cuando escribe O a mano, generalmente 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, esta no funciona con la mayoría de las fuentes, pero es la justificación original de los nombres.
uno es Gran “O”
uno es Gran Theta
http://en.wikipedia.org/wiki/Big_O_notación
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 true para la misma expresión, puede usar la notación theta grande….
Nos puedes añadir valor a nuestra información dando tu experiencia en las explicaciones.