POSCOMP 2019: Questão 22 Resolvida (Notações Assintóticas)

Por
| 

Logotipo do POSCOMP 2019

Questão

Considere as seguintes funções:

$$\begin{gather}f(n)=2^n\\g(n)=n!\\h(n)=n^{\log n}\end{gather}$$

Assinale a alternativa correta a respeito do comportamento assintótico de $f(n)$, $g(n)$ e $h(n)$.

  • (A) $f(n)=O(g(n));g(n)=O(h(n))$
  • (B) $f(n)=\Omega(g(n));g(n)=O(h(n))$
  • (C) $g(n)=O(f(n));h(n)=O(f(n))$
  • (D) $h(n)=O(f(n));g(n)=\Omega(f(n))$
  • (E) Nenhuma das anteriores.

Resolução

Observe que a questão em si consiste basicamente em verificar qual função é assintoticamente maior ou menor que a outra.

Isto é, a partir de qual valor de $n$ suficientemente grande uma função será sempre menor ou maior em comparação com as demais.

Na prática, se soubermos ordenar as funções assintoticamente, podemos resolver o problema.

No blog, já foi abordado que a complexidade fatorial $n!$ é pior que a exponencial $2^n$ e que, consequentemente, $2^n=O(n!)$.

Isso elimina as alternativas B e C, já que é falso dizer que $f(n)=\Omega(g(n))$ (isso seria equivalente a dizer que assintoticamente $2^n \geq n! $, que é falso) e também é falso dizer $g(n)=O(f(n))$.

Todavia, a função $n^{\log n}$ pode ser um pouco confusa (especialmente se levarmos em conta que não foi dado a base do logaritmo, embora, nesse caso, a informação não seja relevante e assumiremos que a base é 2).

Por causa isso, utilizaremos a seguinte tabela (casas decimais foram truncadas), para verificarmos a partir de qual valor de $n$ uma função é maior ou menor que a outra assintoticamente.

$$n$$ $$h(n)=n^{\log_2 n}$$ $$f(n)=2^n$$ $$g(n)=n!$$
1 1 2 1
2 2 4 2
3 5 8 6
4 16 16 24
5 41 32 120
6 102 64 720
7 235 128 5040
8 512 256 40320
9 1058 512 362880
10 2098 1024 3628800
11 4005 2048 39916800
12 7393 4096 4,79×108
13 13245 8192 6,23×109
14 23105 16384 8,72×1010
15 39342 32768 1,31×1012
16 65536 65536 2,09×1013
17 107007 131072 3,56×1014
18 171550 262144 6,40×1015

Observe que a partir do valor $n=17$, já é possível definir a ordem de crescimento das funções.

Por meio dos dados da tabela, verificamos que as funções podem ser colocadas na seguinte ordem (da menor para a maior) em termos de crescimento assintótico: $n^{\log n}$, $2^n$ e $n!$. Portanto, é falso afirmar que $g(n)=O(h(n))$, já que $g(n)=n!$ é assintoticamente maior que $h(n)=n^{\log n}$. Isso elimina a alternativa A.

Analisando a alternativa D, vemos que $h(n)=O(f(n))$ é verdadeiro (isto é, $n^{\log n}=O(2^n)$) e também é verdadeiro dizer que $g(n)=\Omega(f(n))$ (ou seja, $n!=\Omega(2^n)$), pois a função exponencial é assintoticamente menor que a função fatorial.

Em outras palavras, a alternativa correta é a D.

Mais questões

Se você deseja mais questões resolvidas do POSCOMP 2019, acesse a tag Questões do POSCOMP 2019.

Agora, se você procura questões, gabaritos e caderno de questões de outras edições, então acesse a página POSCOMP.

Resolverei as questões conforme o tempo permitir e de acordo com os meus conhecimentos. Como eu não sei resolver todas as questões, recomendo que você consulte também o gabarito oficial do exame.

Obrigado pela leitura! Se você puder, considere apoiar financeiramente o Blog Cyberini. Qualquer valor doado contribui muito para a difusão do conhecimento.

Doar com PagSeguroDoar com PayPal


Siga o blog

Redes sociais: Facebook, Twitter, YouTube, Pinterest, Instagram, Telegram

Receba notificações de novas postagens e novidades do blog por e-mail.

Importante: utilize o bom senso na hora de comentar. Acesse a política de privacidade para maiores informações sobre comentários.

Nenhum comentário:

Postar um comentário