4 votos

Cómo encontrar la suma de Big-Oh?

Tengo que admitir que esta es una tarea problema, pero estoy atascado en serio. Yo no estoy buscando respuestas, pero sólo de cualquier tipo de sugerencias en cuanto a qué hacer a continuación. Cualquier consejo se agradece.

Se me da:
$$f_1(x) = O(g_1(x)): \exists c_1>0 \; \exists x_1 \; \forall x > x_1 \quad \lvert f_1(x)\rvert \le c_1 \cdot \lvert g_1(x)\rvert$$ $$f_2(x) = O(g_2(x)): \exists c_2>0 \; \exists x_2 \; \forall x > x_2 \quad \lvert f_2(x)\rvert \le c_2 \cdot \lvert g_2(x)\rvert$$

Y yo tengo que hacer lo siguiente:

Suponga $g_1$ $g_2$ son no-negativos. Encontrar fórmulas explícitas para $c_3$ $x_3$ (en términos de$c_1, c_2, x_1,$$x_2$) por lo que el $$\text{for all } x > x_3, \lvert f_1(x) + f_2(x) \rvert \le c_3 \cdot \lvert g_1(x) + g_2(x) \rvert$$

Esencialmente estoy demostrando que $f_1(x) + f_2(x) = O(g_1(x) + g_2(x))$.

De la información dada puedo conseguir ese $$ {\lvert f_1(x) \rvert \over \lvert g_1(x)\rvert} \le c_1 \quad \text{and} \quad {\lvert f_2(x) \rvert \over \lvert g_2(x)\rvert} \le c_2$$

Pero aquí es donde me quedo atascado. No tengo idea de cómo proceder. ¿Alguien puede dar algunos consejos?

1voto

Ish Puntos 11

Con la información dada, si fijamos $x > \max\{x_1,x_2 \}$, entonces tenemos

\begin{align} |f_1(x) + f_2(x)| &\leq |f_1(x)| + |f_2(x)| \\ &\leq c_1|g_1(x)| + c_2 | g_2(x)|\\ &\leq \max \{c_1,c_2 \}(g_1(x) + g_2(x)). \quad(\text{since %#%#% are nonnegative} ) \end{align}

Por lo $g_1,g_2$ $c_3 = \max \{c_1,c_2 \}$ como se requiere.

En realidad se puede ir más lejos con este (y es sólo una línea) y muestran que la $x_3 = \max\{x_1,x_2 \}$, pero voy a dejar que usted.

También debo señalar que su pregunta se pide "una fórmula explícita". La fórmula para el máximo de dos números es $f_1 + f_2 \in O(\max \{g_1, g_2 \} )$$

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by: