Qual é a ordem de tempo (complexidade) do seguinte algoritmo em função de N? para i de 1 até N faça para j de…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Utilizar conceitos iniciais de uma linguagem de programação na implementação de algoritmos escritos em linguagem corrente e/ou matemática.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Qual é a ordem de tempo (complexidade) do seguinte algoritmo em função de N? para i de 1 até N faça para j de 1 até N faça corpo constante; fim para; fim para.
- A) O(log N)
- B) O(N²)
- C) O(N)
- D) O(1)
- E) O(N³)
✅ Resposta correta: alternativa B
Resolução passo a passo
- Identifique a estrutura do algoritmo. Há dois laços 'para' aninhados: o laço externo varia i de 1 até N e, a cada valor de i, o laço interno varia j de 1 até N.
- Conte quantas vezes o corpo é executado. O corpo 'constante' (uma operação de custo fixo) roda uma vez para cada par (i, j). Como i assume N valores e, para cada um, j assume N valores, o total é N vezes N, isto é, N^2 execuções.
- Descarte termos e constantes. Como o custo total é N^2 operações de custo constante, a ordem de complexidade é O(N^2), que corresponde à alternativa B.
- Por que as outras estão erradas. A) O(log N) seria típico de algoritmos que dividem o problema pela metade a cada passo, o que não ocorre aqui. C) O(N) ocorreria se apenas um dos laços variasse de 1 a N. D) O(1) indicaria custo constante, independente de N, o que não se aplica, pois os laços dependem de N. E) O(N^3) exigiria um terceiro laço aninhado, que não existe neste algoritmo.
- Conclusão. O gabarito oficial B está correto e coincide com a resolução feita de forma independente.
💡 Dica: Analise a estrutura de repetição do algoritmo.
Alternativa por alternativa
O aluno pode ter associado qualquer laço ou busca a algoritmos de divisão pela metade, como a busca binária, e aplicado logaritmo sem analisar a estrutura dos laços.
Há N iterações externas e N internas por cada externa, totalizando aproximadamente N×N operações.
O aluno pode ter contado apenas o laço externo, ignorando que o laço interno também percorre de 1 até N a cada iteração do externo.
Por que engana: O aluno pode confundir a complexidade de um loop aninhado, subestimando o número total de iterações e escolhendo uma ordem de tempo menor.
O aluno pode ter achado que, por o corpo ser constante, a complexidade total também é constante, esquecendo que o corpo é repetido N vezes em cada um dos N ciclos.
O aluno pode ter supostamente visto dois laços e pensado em um terceiro nível de repetição, ou confundido o expoente pela contagem de laços com o número de execuções.
Raio-X da questão
complexidade de algoritmos
avaliacao
complexidade de algoritmos · análise de loops aninhados
Revisar conceitos de complexidade de algoritmos e notação Big O.
O aluno pode confundir a complexidade de um loop aninhado, subestimando o número total de iterações e escolhendo uma ordem de tempo menor.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Em um dia de trabalho, uma entregadora que usa um aplicativo recebe R$ 12 por entrega. Ela gasta R$ 3 por entrega com…
- Em uma gráfica, a quantidade de tinta adicional é registrada em função de uma medida-padrão q. Para um pedido, a…
- Em uma gráfica, uma máquina imprime livros a uma taxa constante. Se trabalha sozinha, produz 120 páginas por hora…
- — O desconto só incide sobre as oficinas, não sobre a entrada — explicou a atendente a um visitante. Na feira municipal…
- Uma associação de ambulantes realizou uma pesquisa sobre o gasto mensal com internet móvel. Os dados foram organizados…
- Uma secretaria municipal recebeu R$ 390 para inscrever dois agentes em um curso, ambos com o mesmo número de oficinas…
🔎 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