Coloque F (falso) ou V (verdadeiro) nas funções abaixo, con...

Próximas questões
Com base no mesmo assunto
Q1759874
Algoritmos e Estrutura de Dados Algoritmos , Complexidade de Algoritmos ,
Ano: 2020 Banca: Marinha Órgão: Comando do 2º Distrito Naval Prova: Marinha - 2020 - Comando do 2º Distrito Naval - Informática |
Q1759874 Algoritmos e Estrutura de Dados

Coloque F (falso) ou V (verdadeiro) nas funções abaixo, considerando a notação de complexidade O, e assinale a seguir a opção correta.


( ) f - 9 + log n = 0(n)

( ) f= 255 = 0(1)

( ) f = 37 + 215n = 0(2n)

( ) f=25 + 218+n = 0(2n)

Alternativas

Gabarito comentado

Confira o gabarito comentado por um dos nossos professores

Gabarito: B

Fundamento decisivo: O critério decisivo é a definição operacional de Big-O: verificar se a função dada é limitada superiormente por um múltiplo constante da função de referência a partir de certo n. Isso orienta a leitura das quatro sentenças e leva à sequência V, V, F, V, que corresponde à alternativa B.

Tema central: Classificação por Big-O
Análise das alternativas
A
Errada
Está errada porque inverte exatamente as duas sentenças exponenciais. A terceira não é verdadeira: 2^(15n) não é O(2^n), pois altera a taxa de crescimento. A quarta não é falsa: 2^(18+n) = 2^18·2^n, e esse fator 2^18 é constante multiplicativa, que não altera a classe O(2^n).
B
Certa
A alternativa B está correta porque corresponde à sequência tecnicamente válida do enunciado.
C
Errada
Está errada já nas duas primeiras marcações. 9 + log n é O(n), porque o termo linear domina o logarítmico e a constante aditiva é desprezada na classificação assintótica. Além disso, 255 é O(1), pois qualquer constante positiva pertence à classe constante.
D
Errada
Está errada porque marca a primeira sentença como falsa e a terceira como verdadeira, mas o correto é o oposto. 9 + log n pertence a O(n), enquanto 37 + 2^(15n) não pertence a O(2^n), já que 2^(15n) cresce muito mais rapidamente que 2^n.
E
Errada
Está errada porque nega a segunda e a quarta sentenças, ambas verdadeiras. A função 255 é constante, logo é O(1). Já 25 + 2^(18+n) pertence a O(2^n), porque 2^(18+n) pode ser reescrita como constante vezes 2^n, e nem a constante multiplicativa nem a constante aditiva mudam a classe assintótica.
Pegadinha da questão
A confusão real está em tratar 2^(15n) e 2^(18+n) como se fossem alterações equivalentes de 2^n. Não são: em 2^(15n), o expoente foi multiplicado por 15, mudando a taxa de crescimento; em 2^(18+n), o 18 gera apenas um fator constante multiplicativo fora da exponencial dominante.
Dica para questões semelhantes
  • Em Big-O, verifique se a função pode ser limitada superiormente por c·g(n) para n suficientemente grande; não leia o símbolo como igualdade algébrica literal.
  • Despreze constantes aditivas e multiplicativas ao comparar ordens de crescimento, mas não despreze mudanças que alteram a taxa de crescimento no expoente.
  • Separe expressões exponenciais antes de classificar: 2^(a+n) = 2^a·2^n, mas 2^(an) não é mera constante vezes 2^n.
  • Lembre que O(g(n)) admite cota superior não exata: uma função menor, como log n, pode pertencer a O(n).

Clique para visualizar este gabarito

Visualize o gabarito desta questão clicando no botão abaixo

Comentários

Veja os comentários dos nossos alunos

Quando se fala de complexidade utilizando o BIG O, pode-se desprezar constantes aditivos e multiplicativas.

Nesse caso a questão está querendo saber qual é a complexidade de pior caso. Para saber isso é necessário saber quais são as possíveis complexidades e sua ordem.

O(1) = Constante

O(log n) = logarítmica

O(log^2 n) = log quadrática

O(n log n) = n log n

O(n) = linear

O(n^2) = quadrática

O(n^3) = cubica

O(2^n) = exponencial

================================

f - 9 + log n = 0(n) => CERTO

f= 255 = 0(1) => CERTO

f = 37 + 215n = 0(2n) => ERRADO - O(2^15N) possui a maior complexidade que a O(2^n)

f=25 + 218+n = 0(2n) => CERTO

Alternativa: B

Clique para visualizar este comentário

Visualize os comentários desta questão clicando no botão abaixo

Questões de assuntos semelhantes

Provas relacionadas