Durante os testes de desempenho de um algoritmo de compressão de dados, os desenvolvedores registraram o…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Investigar relações entre números expressos em tabelas para representá-los no plano cartesiano, identificando padrões e criando conjecturas para generalizar e expressar algebricamente essa generalização, reconhecendo quando essa representação é de função polinomial de 2º grau do tipo y = ax2.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Durante os testes de desempenho de um algoritmo de compressão de dados, os desenvolvedores registraram o número de operações básicas executadas para diferentes tamanhos de entrada n (n representa a quantidade de blocos de dados): n | 1 | 2 | 3 | 4 | 5 Operações | 2 | 4 | 8 | 16 | 32 Com esses valores, os engenheiros perceberam um padrão de crescimento e desejam generalizar esse comportamento para qualquer valor de n. A partir dos dados do texto-base, elabore a expressão que modela o número de operações O(n) em função de n e formule a conjectura que descreve o padrão de crescimento desse algoritmo.
- A) O(n) = 2 · n
- B) O(n) = n!
- C) O(n) = n^2
- D) O(n) = n · log n
- E) O(n) = 2^n
✅ Resposta correta: alternativa E
Resolução passo a passo
- Observe a tabela. Para n=1 temos 2 operações, n=2 temos 4, n=3 temos 8, n=4 temos 16 e n=5 temos 32.
- Calcule a razão entre termos consecutivos: 4/2=2, 8/4=2, 16/8=2, 32/16=2. Como a razão é constante e igual a 2, o crescimento é multiplicativo, não aditivo.
- Procure a forma geral. Cada valor é 2 vezes o anterior, então O(n)=2^n, pois 2^1=2, 2^2=4, 2^3=8, 2^4=16 e 2^5=32, coincidindo com todos os dados.
- Verifique as alternativas. A) 2·n daria 2, 4, 6, 8, 10, que não cresce como os dados. B) n! daria 1, 2, 6, 24, 120, que não confere com n=3 (8 operações). C) n^2 daria 1, 4, 9, 16, 25, que não confere com n=1 nem com n=3. D) n·log n não gera potências de 2 e não coincide com os valores tabelados.
- Conclusão: a expressão que modela os dados é O(n)=2^n, e a conjectura é que o número de operações dobra a cada novo bloco de dados, caracterizando crescimento exponencial de base 2. Gabarito oficial confirmado.
💡 Dica: Observe o padrão de crescimento e relacione com funções comuns de complexidade.
Alternativa por alternativa
O aluno percebeu que os valores crescem e tentou ajustar uma função linear, sem verificar a razão entre termos consecutivos, que não é constante na diferença (2, 4, 8, 16, 32 aumentam de forma não linear).
O aluno confundiu crescimento muito rápido com fatorial, supondo que a função cresce como n! sem testar os valores da tabela, já que 3! = 6 e não 8.
O aluno ajustou uma função polinomial quadrática por intuição de crescimento acelerado, sem checar que n^2 fornece 9 para n=3 e 25 para n=5, valores diferentes dos registrados.
Por que engana: Confundir crescimento exponencial com crescimento linear ou quadrático, escolhendo funções inadequadas.
O aluno associou algoritmos de compressão à complexidade n log n, um modelo muito comum em estudos de algoritmos, sem perceber que os dados da tabela seguem potências de 2 e não essa forma.
Os valores dobram a cada incremento de n, caracterizando crescimento exponencial de base 2, ou seja, O(n)=2^n.
Raio-X da questão
complexidade algorítmica exponencial
avaliacao
funções matemáticas básicas · análise de algoritmos
Estude funções de crescimento exponencial e análise de algoritmos.
Confundir crescimento exponencial com crescimento linear ou quadrático, escolhendo funções inadequadas.
ciencia_tecnologia
pensamento_critico
cientifico
Questões parecidas com resolução
- Em uma feira de artesanato, uma artesã organiza enfeites em fileiras para montar uma vitrine. Na primeira fileira, ela…
- No ateliê de encadernação da rua das Palmeiras, uma máquina separa etiquetas para caixas de presente. Na primeira…
- Dados ilustrativos de teste de um novo jogo mostram como variou a pontuação p obtida ao concluir determinados níveis n…
- Em uma oficina de mosaicos, uma sequência de painéis usa 3, 8, 15 e 24 peças, nessa ordem. A equipe percebeu que a…
- Técnicos de um arquivo digital organizam cópias de segurança em níveis numerados a partir de 0. Para ampliar a…
- Em um simulador, Ana registrou os resultados de 2 × n para n = 1, 2, 3, 4, 5 e 6. Ela quer escrever, em linguagem…
🔎 Procurar outra questão
Procure no banco do GeraProva pelo tema ou por um trecho do enunciado. Cada questão já vem com resolução comentada e a análise de cada alternativa.
Professor: monte a prova com questões como esta, com gabarito e folha de respostas, em 30 segundos. Ver planos · Blog