¿Diferentes definiciones de la notación Big O?

Question

¿Diferentes definiciones de la notación Big O?

limites
análisis
asintóticos
Matemáticas
análisis real

pipí

No estoy muy familiarizado con el análisis formal, así que probablemente esté pensando en esto de forma incorrecta. He mirado varias publicaciones en SE en notación de O grande. Lo más cercano a mi consulta parecía ser este , pero no llegó a mi dificultad...

Estaba mirando la definición de la notación Big-O. Cuando la notación Big-O se pasó por alto en las conferencias, la definición se dio como " $f(x)=O(g(x))$ como $x\to a$ si existe un $c\geq 0$ y $\delta \geq 0$ calle $|f(x)|\leq c|g(x)|$ para todos $|x-a|<\delta$ (Ahora sé que sería más correcto decir $f(x)\in O(g(x))$ )

En primer lugar, parece que Wikipedia excluye el punto $x=a$ de esto, que encuentro confuso. Wolfram Alpha no da una definición como esta, y en algunas notas de conferencias de MIT OCW aquí, la definición incluye el punto $x=a$ , como en mis conferencias. Esperando que alguien pudiera aclarar esto.

Mi principal dificultad, sin embargo, es reconciliar esta definición formal con la definición más prolija de " $f(x)\in O(g(x))$ medio $f$ tiene una tasa de crecimiento que es menor o igual a la de $g$ ".

Estaba tratando de averiguar cómo estas dos definiciones son equivalentes, pero tenía algunos problemas. Pasando de la primera a la segunda definición, he dicho

$\frac{f(x)-f(a)}{x-a} \leq \frac{cg(x)-f(a)}{x-a}$ tomando ambas funciones como positivas por ahora.

pero entonces no creo que haya nada más que pueda decir. Estaba tratando de mostrar que la derivada (tasa de crecimiento) de $f$ debe ser menor que el de $g$ pero el problema es que, aunque $f(a)\leq c(g(a))$ es la forma de definición que tienen mis conferencias (donde se incluye x=a), no puedo decir que $cg(x)-cg(a)\geq f(x)-f(a)$ . E incluso un boceto muestra que este no tiene por qué ser el caso:

Entonces pensé que tal vez la definición con respecto a la tasa de cambio se aplicaba solo al caso de $a=\infty$ , pero de nuevo tengo problemas para probar esto porque f podría moverse por debajo de g hasta el infinito, por lo que es difícil hablar de gradientes.

¿Quizás estoy pensando en este error y la notación Big-O se refiere al enfoque en una escala global en lugar de local? Entonces, en algunos lugares, puede ser el caso de que la tasa de crecimiento de f exceda la de g, pero no en general o, de lo contrario, ¿f eventualmente superaría a g?

Arte simplemente hermoso

Creo que estás confundiendo lo que significa "tasa de crecimiento". En particular, está analizando la velocidad a la que

f (x) \to f (a)

$f(x)\to f(a)$ en comparación con la velocidad a la que

g (x) \to g (a)

$g(x)\to g(a)$ , dónde

f

$f$ y

g

$g$ son continuos. Por ejemplo,

x

$x$ enfoques

0

$0$ más lento que

x^{2}

$x^2$ .

Masacroso

grande-Oh en un punto

a

$a$ de una función

f

$f$ significa que

| f |

$|f|$ está delimitado por

M | g |

$M |g|$ (para algunos

M > 0

$M>0$ y alguna funcion

g

$g$ ) en un barrio de

a

$a$ . Entonces decimos que

f \in O (g), x \to a

$f\in\mathcal O(g), x\to a$ .

Respuestas (1)

¿Diferentes definiciones de la notación Big O?

Creo que estás confundiendo lo que significa "tasa de crecimiento". En particular, está analizando la velocidad a la que $f(x)\to f(a)$ en comparación con la velocidad a la que $g(x)\to g(a)$ , dónde $f$ y $g$ son continuos. Por ejemplo, $x$ enfoques $0$ más lento que $x^2$ .
grande-Oh en un punto $a$ de una función $f$ significa que $|f|$ está delimitado por $M |g|$ (para algunos $M>0$ y alguna funcion $g$ ) en un barrio de $a$ . Entonces decimos que $f\in\mathcal O(g), x\to a$ .

GEdgar · Answer 1

¿Por qué excluiríamos el punto $a$ ? Es posible que queramos decir

\frac{1}{pecado t} = O (\frac{1}{t}) como t \to 0

$\frac{1}{\sin t} = O\left(\frac{1}{t}\right)\qquad\text{as } t \to 0$ aunque ambas funciones no están definidas en

t = 0

$t=0$ .

Como en ese ejemplo: cuando usamos el lenguaje de "tasa de crecimiento", probablemente estemos pensando que ambos $f$ y $g$ ir a $\infty$ . Así que estamos preguntando si uno de ellos va a $\infty$ más rápido que el otro.

¿Diferentes definiciones de la notación Big O?

pipí

Arte simplemente hermoso

Masacroso

Respuestas (1)

GEdgar

¿Cuál es exactamente la relación y cuáles son las diferencias entre los límites multivariables y los límites complejos?

Demostrar que existe una derivada dado el límite de f'

¿Límite de secuencia, teorema de compresión?

¿Cuáles son exactamente las diferencias entre los límites multivariables reales y los límites complejos?

¿Toda función continua tiene un orden de desaparición?

inf(A+B)=infA+infBinf(A+B)=infA+infB\inf{(A+B)}=\inf{A}+\inf{B}: Una prueba de ϵϵ\epsilon

Del razonamiento detrás del teorema del valor medio

Evaluar limn→∞xnn√limn→∞xnn\lim_{n\to\infty}\frac{x_n}{\sqrt n}

Diferente definición de continuidad.

Vladímir Zorich contra Rudin/Pugh/Abbott