Considere las siguientes funciones
¿Cual de los siguientes es verdadero?
(A) h(n) es O(f(n))
(B) h(n) es O(g(n))
(C) g(n) no es O(f(n))
(D) f(n) es O(g(n))
Respuesta: (D )
Explicación: notación Big-oh:
Sean f y g dos funciones definidas sobre un número real. Se escribe f(n) = O(g(n)) si existe una constante positiva M tal que para todos los valores suficientemente grandes de n, el valor absoluto de f(n) es como máximo M multiplicado por el valor absoluto de g (norte). Es decir, f(n) = O(g(n)) si y solo si existe un número real positivo M y un número real n0 tal que f(n)≤M(g(n)), para todo n≥ n0.
En la notación Big-oh, solo hacemos una comparación entre dos funciones considerando valores más grandes de n. Para resolver preguntas como esta, podemos tomar un valor mayor de n y luego comparar los valores de diferentes funciones.
f(n) = 3(n^32)=3*(2^10)^32=3*2^320
g(n) = 2^320
h(n)=1024!
Entonces la relación entre las funciones puede ser:
1.f(n) y g(n) son del mismo orden, entonces f(n) es O(g(n)) y g(n)=O(f(n)). Por lo tanto, la opción C es incorrecta.
2.h(n) es n! Que es de orden superior a f(n) y g(n). Entonces las opciones A y B son incorrectas.
Ver http://geeksquiz.com/algorithms-analysis-of-algorithms-question-22/
Esta solución es aportada por Nirmal Bharadwaj
Cuestionario de esta pregunta
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA