¿Puedo decir que [matemáticas] 4 ^ {2n} = O (4 ^ {2n}) [/ matemáticas]?

Answer 1

Tl; dr Sí

Un recordatorio rápido del significado de Big-Oh [1]

[matemática] f (n) = O (g (n)) \ iff [/ matemática] existen constantes positivas [matemática] c, n_0 [/ matemática] tal que [matemática] 0 \ leq f (n) \ leq cg (n) [/ math] para todos [math] n> n_0 [/ math]

En ese sentido, si hacemos [matemáticas] c = 1, [/ matemáticas] [matemáticas] n_0 = 0 [/ matemáticas] y [matemáticas] f (n) = 4 ^ {2n} [/ matemáticas] entonces para todas [matemáticas ] n> n_0 [/ matemáticas]

[matemáticas] 0 \ leq f (n) \ leq cf (n) [/ matemáticas]

Entonces [matemáticas] f (n) = O (f (n)) [/ matemáticas]

Nota: siguiendo esta intuición, para cualquier función positiva [matemática] f (n) [/ matemática] podemos decir que [matemática] f (n) = [/ matemática] [matemática] O (f (n)) [/ matemática ]

Notas al pie

[1] Introducción a los algoritmos

Answer 2

Correcto, puede indicar esto (siempre y cuando comprenda que “=” es una convención para “está adentro” o “está”).

Big-Oh tiene la propiedad reflexiva . Es decir, para cualquier función de crecimiento [matemática] f (n) [/ matemática], [matemática] f (n) \ en O (f (n)) [/ matemática].

Answer 3

4 ^ (2n) es una expresión matemática. En el contexto del análisis de algoritmos, consideramos que 4 ^ (2n) es una función, g (n).

O (4 ^ 2n), conocido como Big-Oh de 4 ^ 2n, es una estadística de orden para algoritmos. Se conoce como el límite superior asintótico para un algoritmo. O (4 ^ 2n) y 4 ^ 2n, son objetos diferentes que no pueden ser igualados.

Se dice que un proceso o algoritmo que es O (4 ^ 2n) es de complejidad 4 ^ 2n en el peor de los análisis del algoritmo. En otras palabras, su escala no es peor que 4 ^ 2n. Puede escalar mejor que 4 ^ 2n pero no escalará peor que 4 ^ 2n en un tamaño de entrada de n.

Nota: Estoy de acuerdo con las otras respuestas dadas. 4 ^ 2n = 16 ^ n de aritmética. Sin embargo, al estudiar algoritmos, si la naturaleza del problema se representa mejor como 4 ^ (2n) porque 4 ^ (2n) refleja la estructura del problema o proporciona una idea de los aspectos operativos del algoritmo, preferiría ver representaba en su forma no reducida.

Por ejemplo, una estructura de 4 nodos que se procesa exponencialmente 2n veces, en lugar de reducirla a 16 ^ n, que no refleja la estructura original de 4 nodos.

Answer 4

Primero entendamos la notación Big-Oh representada simbólicamente como O.

Sean f (n) yg (n) dos funciones positivas yc es una constante y mayor que cero.

f (n) = O (g (n)) si y solo si: –

f (n) <= c * g (n).

Ahora se nos da la relación:

4 ^ (2n) = O (4 ^ (2n)) ………………. (1)

para que la relación (1) sea verdadera:

4 ^ (2n) <= c * 4 ^ (2n)

tomar c = 1;

4 ^ (2n) <= 1 * 4 ^ (2n)

4 ^ (2n) <= 4 ^ (2n)

lo cual es absolutamente correcto para todos los valores de n.

Por lo tanto, la relación 4 ^ (2n) = O (4 ^ (2n)) es válida.

Answer 5

Cualesquiera convenciones en torno a la notación que esté utilizando, sí puede. Es incómodo, ya que es más complejo de lo necesario, porque 16 ^ N es mucho más ordenado. En la complejidad algorítmica, muchos simplemente dirían a ^ n porque la forma amplia del término dominante suele ser más importante, pero el valor de a obviamente importa si dos algoritmos son ambos O (a ^ n).