Questão FC373203
Uma Analista de Sistemas da Câmara Legislativa ficou com a tarefa de verificar a complexidade dos trechos de algoritmo em pseudocódigo abaixo. Trecho de Algoritmo 1: para i\(\lefta
Algoritmos e Lógica de Programação
FCC · 2018
Uma Analista de Sistemas da Câmara Legislativa ficou com a tarefa de verificar a complexidade dos trechos de algoritmo em pseudocódigo abaixo.
Trecho de Algoritmo 1:
para i\(\leftarrow\)1 até n passo 1 faça
para j\(\leftarrow\)1 até n passo 1 faça
mat[i][j] \(\leftarrow\) mat1[i][j] + mat2[i][j];
fim_para
fim_para
Trecho de Algoritmo 2:
aux \(\leftarrow\) vet[1]
para j\(\leftarrow\)1 até n passo 1 faça
se (vet[j] > aux)
então
aux \(\leftarrow\) vet[j]
fim_se
fim_para
Trecho de Algoritmo 3:
para i\(\leftarrow\)1 até n passo 1 faça
para j\(\leftarrow\)1 até n passo 1 faça
mat[i][j] \(\leftarrow\) 0
para k\(\leftarrow\)1 até n passo 1 faça
mat[i][j] \(\leftarrow\) mat[i][j] + (mat1[i][k] * mat2[k][j])
fim_para
fim_para
fim_para
Considerando que o valor de n é maior que 1, a Analista conclui corretamente que
- todos os trechos têm complexidade n, pois todos os comandos de repetição trabalham com n como limite.
- os trechos 1 e 2 sempre terão melhor desempenho que o trecho 3, para os mesmos e altos valores de n.
- todos os trechos podem ser executados em tempos polinomiais (em até algumas horas) para todos os valores de n.
- o trecho 1 tem o mesmo desempenho que o trecho 3, ou seja, suas complexidades são as mesmas.
- o trecho 3 tem complexidade 2n, por isso é o único trecho que pode se tornar inviável em tempos polinomiais.
Mostrar resposta e comentário
Gabarito
B
Comentário do professor
A alternativa está correta porque comparamos a **complexidade de tempo** dos trechos usando a notação Big O. Cada laço aninhado multiplica a ordem do crescimento.
No trecho 2 há um único laço: complexidade \(O(n)\).
No trecho 1 há dois laços aninhados (i e j): complexidade \(O(n^2)\).
No trecho 3 há três laços aninhados (i, j e k): complexidade \(O(n^3)\).
Assintoticamente, para \(n\) grandes vale \(O(n) < O(n^2) < O(n^3)\). Ou seja, o custo do trecho 3 cresce muito mais rápido — por exemplo, se \(n=10^3\), então \(n^2=10^6\) e \(n^3=10^9\). Logo, os trechos 1 e 2 sempre terão melhor desempenho que o trecho 3 para os mesmos e altos valores de \(n\).
Conteúdo do catálogo FC Concursos · Atualizado em