Em um programa, um laço for percorre todos os n elementos de um vetor. Em cada repetição, o programa atualiza…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Elaborar algoritmos que envolvam instruções sequenciais, de repetição e de seleção usando uma linguagem de programação.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Em um programa, um laço for percorre todos os n elementos de um vetor. Em cada repetição, o programa atualiza uma variável acumuladora com uma operação simples. Qual é a ordem de crescimento do tempo de execução desse trecho em função de n?
- A) A ordem de crescimento é quadrática: O(n²).
- B) A ordem de crescimento é constante: O(1).
- C) A ordem de crescimento é logarítmica: O(log n).
- D) A ordem de crescimento é linear: O(n).
- E) A ordem de crescimento é exponencial: O(2^n).
✅ Resposta correta: alternativa D
Resolução passo a passo
- Identifique o que o trecho faz. Um laço for percorre todos os n elementos do vetor, uma vez para cada elemento.
- Analise o custo por repetição. Em cada volta, o programa executa apenas uma operação simples sobre a variável acumuladora, que leva um tempo fixo, independente de n.
- Calcule o total. Como há n repetições e cada uma custa um tempo constante c, o tempo total é aproximadamente c * n. Desprezando constantes e termos menores, isso é O(n).
- Compare com o gabarito. Resolvi a questão de forma independente e cheguei à alternativa D, que coincide com o gabarito oficial.
- Por que as outras estão erradas. A) O(n²) exigiria um laço aninhado dentro do for, o que não existe aqui. B) O(1) significaria tempo fixo, mas o número de repetições cresce com n. C) O(log n) apareceria se o tamanho do problema fosse dividido ao meio a cada passo, o que não ocorre em um percorrimento simples. E) O(2^n)描述 crescimento exponencial, típico de recursões que se ramificam, não de um único laço.
💡 Dica: Considere a estrutura do laço e a quantidade de iterações.
Alternativa por alternativa
O aluno imagina que qualquer laço gera crescimento quadrático, confundindo um for simples com dois laços aninhados.
Por que engana: Confundir a ordem de crescimento linear com a quadrática, acreditando que o laço simples gera uma complexidade maior do que realmente é.
O aluno acredita que, como a operação dentro do laço é simples, o tempo total também não depende de n, esquecendo que ela se repete n vezes.
O aluno associa qualquer estrutura de repetição a O(log n), confundindo com algoritmos de divisão do problema, como a busca binária.
O laço executa uma vez para cada um dos n elementos do vetor. Como a operação realizada em cada repetição tem tempo constante, o tempo total cresce na mesma proporção que n, resultando em O(n).
O aluno confunde crescimento exponencial com repetição comum, supondo que laços sempre geram crescimento muito rápido, como em certas recursões.
Raio-X da questão
ordem de crescimento
avaliacao
complexidade de algoritmos · laços de repetição
Revisar conceitos de complexidade de algoritmos e laços de repetição.
Confundir a ordem de crescimento linear com a quadrática, acreditando que o laço simples gera uma complexidade maior do que realmente é.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Um algoritmo percorre um vetor de n números e soma seus elementos uma única vez. Qual é a complexidade temporal desse…
- Um algoritmo percorre uma lista de n elementos com dois loops aninhados: para i de 1 a n: para j de 1 a n: executar…
- Considere um algoritmo com duas estruturas de repetição aninhadas, cada uma iterando de 1 até n. Qual é a complexidade…
- Considere o algoritmo: contador := 0; para i de 1 até n passo 2 faça contador := contador + 1; fim para. Em termos de n…
- Num algoritmo que percorre uma sequência de N elementos com um laço 'para' (repetição) usando a variável índice 'i'…
- Considere o pseudocódigo: soma <- 0; para i de 1 até 5: leia x; soma <- soma + x; fimPara; escreva(soma/5). Qual…
🔎 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