Um professor acompanha o tempo de execução de um algoritmo para diferentes tamanhos de entrada: n=100, 200…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Identificar o comportamento dos algoritmos no que diz respeito ao consumo de recursos como tempo de execução, espaço de memória e energia, entre outros.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Um professor acompanha o tempo de execução de um algoritmo para diferentes tamanhos de entrada: n=100, 200, 400, 800, 1600; tempos em ms: 5, 10, 20, 40, 80. O que isso sugere sobre a relação entre tempo de execução e n?
- A) O tempo cresce aproximadamente em proporção direta a n (complexidade linear).
- B) O tempo cresce com complexidade quadratic (O(n^2)).
- C) O tempo independe de n.
- D) O tempo cresce com complexidade logarítmica (O(log n)).
- E) O tempo diminui conforme n aumenta.
✅ Resposta correta: alternativa A
Resolução passo a passo
- Observe como o tempo varia quando n dobra. De n=100 para n=200, n dobra e o tempo vai de 5 ms para 10 ms, ou seja, também dobra. De 200 para 400, o tempo vai de 10 para 20 ms. De 400 para 800, de 20 para 40 ms. De 800 para 1600, de 40 para 80 ms.
- Calcule a razão entre tempos consecutivos: 10/5 = 2, 20/10 = 2, 40/20 = 2, 80/40 = 2. A razão é constante e igual à razão entre os tamanhos de entrada (2). Isso indica que o tempo é proporcional a n, ou seja, t(n) = k·n, com k = 0,05 ms por unidade de n (5/100).
- Uma relação de proporção direta entre tempo e n é o que se chama de complexidade linear, O(n). Portanto a alternativa A está correta e coincide com o gabarito oficial.
- Por que as outras estão erradas. B: se fosse quadrática, dobrar n multiplicaria o tempo por 4, e aqui o tempo só dobra. C: se o tempo independesse de n, ele permaneceria constante, o que não ocorre, pois ele cresce de 5 para 80 ms. D: se fosse logarítmica, dobrar n somaria um valor fixo ao tempo, e não o dobraria. E: o tempo aumenta em todas as medições, então não diminui conforme n cresce.
- Observação: como são apenas cinco pontos medidos, a conclusão é uma sugestão a partir dos dados, e não uma prova formal da complexidade do algoritmo, que depende de sua análise teórica e de fatores como o hardware.
💡 Dica: Compare como os tempos variam quando n dobra.
Alternativa por alternativa
A observação de que o tempo dobra quando n dobra é típico de uma relação linear, ou seja, O(n).
O aluno pode ter associado a ideia de que 'algoritmos com laço aninhado' ou 'crescimento acelerado' são sempre quadráticos, sem verificar os dados. Ele não calculou como o tempo responde a dobrar n.
Por que engana: O aluno pode confundir crescimento linear com quadrático, logarítmico ou interpretar que o dobro de n deve produzir um aumento não proporcional no tempo.
O aluno pode ter visto o tempo pequeno e a tabela sem analisar a sequência, ou ter pensado que tempos de execução medidos devem ser constantes. Não percebeu que o tempo cresce de 5 para 80 ms conforme n aumenta.
O aluno pode ter confundido crescimento lento com logaritmo, ou assumido que algoritmos eficientes sempre são logarítmicos. Não notou que, em uma função logarítmica, dobrar n não dobra o tempo.
O aluno pode ter lido a tabela de cima para baixo como se os valores de tempo caíssem, ou ter invertido a relação entre n e o tempo. Os tempos aumentam em todas as medições, e não diminuem.
Raio-X da questão
Complexidade linear de algoritmos
avaliacao
Crescimento de funções · Noção de algoritmo
Revise como identificar complexidades pela variação dos tempos de execução.
O aluno pode confundir crescimento linear com quadrático, logarítmico ou interpretar que o dobro de n deve produzir um aumento não proporcional no tempo.
ciencia_tecnologia
pensamento_critico
cientifico
Questões parecidas com resolução
- Em um projeto de monitoramento de rios, uma boia computacional organiza leituras de sensores antes de enviá-las por…
- Uma biblioteca escolar recebeu caixas de livros doados para uma feira de troca. Para registrar os exemplares, a equipe…
- Um centro cultural público oferece inscrições on-line para atividades com critérios variados. Na oficina de teatro…
- Uma escola está testando dois protótipos de aplicativo para que estudantes consultem mudanças de sala, horários e…
- Uma secretaria municipal de educação está digitalizando pedidos de transporte escolar e de atendimento em contraturno…
- — O cartaz não pode sair duas vezes, pois a feira começa em uma hora — alertou a coordenadora do centro cultural. No…
🔎 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