Si f (n) est Omega (g (n)) alors 2^(f (n)) est Oméga (2^g (n)). Est-ce vrai ou faux

Question

Pour cette question, je pensais que c'est vrai parce que je pensais que la question demande essentiellement f(n) est supérieure ou égale à g(n) est alors 2^(f(n)) supérieure ou égale à 2^(g(n))

Donc, si nous prenons une instance de f(n) = 2n et g(n) = n, f(n) est > g(n). Alors 2^2n est supérieur à 2^n.

Mais mon ami a dit que ce n'était pas correct, quelqu'un peut-il me donner un aperçu? Je pense que je pourrais avoir un malentendu sur le problème.

Answer 1

Pour cette question, je pensais que c'est vrai parce que je pensais que la question demande essentiellement f(n) est supérieure ou égale à g(n) est alors 2^(f(n)) supérieure ou égale à 2^(g(n))

Non. Ce n'est pas du tout ce que signifie la notation grand-omega. f(n) = Ω(g(n)) signifie que pour n suffisamment grand, le ratio f(n)/g(n) est limité ci-dessous par une constante positive.

Pour voir que f(n) = Ω(g(n)) n'implique pas 2^f(n) = Ω(2^g(n)), considérer f(n) = n - log(n) et g(n) = n. Puis 2^f(n) = (2^n)/n et 2^g(n) = 2^n, et 2^f(n) != Ω(2^g(n)).

Answer 2

Vous êtes intéressé à prouver ou d'infirmer cette affirmation:

Si f (n) = Ω (g (n)), puis 2 ^{f (n) =} Ω (2 ^{g (n)}).

Lorsque vous voyez une déclaration comme celle-ci, il est souvent utile de clarifier ce que f et g sont ici. Plus précisément, le rapport ci-dessus vraiment signifie ce qui suit:

Pour toutes les fonctions f et g, si f (n) = Ω (g (n)), puis 2 ^{f (n)} = Ω (2 ^{g (n)})

en ce sens, si vous voulez prouver que cette affirmation est vraie, vous aurez besoin de l'approcher en montrant que cette affirmation est vraie pour tout choix possible f et g, pas seulement en choisissant un seul f et une seule fonction sur g et confirmant que la relation est valable pour ces fonctions particulières. En ce sens, votre ami est correct.

(D'autre part, si vous voulez démentir cette affirmation, il vous suffit de donner des exemples de fonctions f et g où f (n) = Ω (g (n)), mais 2 ^{f (n)} ≠ Ω (2 ^{g (n)}).

Comme indice pour cette question: les notations asymptotiques comme O, Ω et Θ ignorent complètement les facteurs constants. Si f (n) = Ω (g (n)), alors vous pouvez redimensionner f ou g par n'importe quel facteur constant que vous souhaitez et la relation sera toujours maintenue. D'autre part, les facteurs constants dans un exposant changent radicalement les propriétés de cet exposant. par exemple, la fonction e ⁿ croît de façon exponentielle plus lente que la fonction e ²ⁿ, puisque e ^{2n =} (e) ⁿ, qui est une fonction exponentielle avec une base supérieure. En d'autres termes, vous ne pouvez pas mettre à l'échelle les exposants par un facteur constant sans changer complètement leur taux de croissance. Basé sur cette déconnexion - que la notation Ω ne peut pas distinguer les fonctions qui diffèrent par un facteur constant, mais que les fonctions exponentielles sont très sensibles aux facteurs constants - pensez-vous que cette déclaration est vraie ou fausse? Sur la base des conseils ci-dessus, comment pourriez-vous prouver une déclaration comme celle-là?