Considere o algoritmo em pseudocódigo, descrito a seguir. Calcule a complexidade do algoritmo, sabendo que a função f tem complexidade igual a O(...
Considere o algoritmo em pseudocódigo, descrito a seguir.
Calcule a complexidade do algoritmo, sabendo que a função f tem complexidade igual a O(n22).
O(n33log(n))
O(n55)
O(n22log22(n))
O(n33) O(n44log(n))
Data Resp.: 11/03/2023 09:14:03
Explicação:
Vamos analisar o código simplificado abaixo:
J=1
Enquanto j < n
J = 2xj
Para k = 0 ate j
Operação elementar
Para facilitar, vamos fazer n = 2k
J = 1 → j = 2, com 3 (21+1) iterações
J = 2 → j = 4 com 5 (22+1 )iterações
J= 4 → j = 8 com 9 (23+1) iterações
J = 8 → j = 16 com 17 (24+1) iterações
J = 2k → j = (2k+1 + 1) iterações
O total de iterações é a
soma ∑logni=1(2i+1)<2k∑lognj=11=2klogn∑�=1����(2�+1)<2�∑�=1����1=2�����,
porém 2k=n, assim a complexidade do código é n log n. Considerando OP com complexidade constante.
Como OP é quadrática, temos que o código analisado é n3log n.
O for mais externo se repete n vezes, assim a complexidade total do algoritmo é n4log n
O(n33log(n))
O(n55)
O(n22log22(n))
O(n33) O(n44log(n))
Calcule a complexidade do algoritmo, sabendo que a função f tem complexidade igual a O(n22).
O(n33log(n))
O(n55)
O(n22log22(n))
O(n33) O(n44log(n))
Data Resp.: 11/03/2023 09:14:03
Explicação:
Vamos analisar o código simplificado abaixo:
J=1
Enquanto j < n
J = 2xj
Para k = 0 ate j
Operação elementar
Para facilitar, vamos fazer n = 2k
J = 1 → j = 2, com 3 (21+1) iterações
J = 2 → j = 4 com 5 (22+1 )iterações
J= 4 → j = 8 com 9 (23+1) iterações
J = 8 → j = 16 com 17 (24+1) iterações
J = 2k → j = (2k+1 + 1) iterações
O total de iterações é a
soma ∑logni=1(2i+1)<2k∑lognj=11=2klogn∑�=1����(2�+1)<2�∑�=1����1=2�����,
porém 2k=n, assim a complexidade do código é n log n. Considerando OP com complexidade constante.
Como OP é quadrática, temos que o código analisado é n3log n.
O for mais externo se repete n vezes, assim a complexidade total do algoritmo é n4log n
O(n33log(n))
O(n55)
O(n22log22(n))
O(n33) O(n44log(n))
💡 1 Resposta
Ed 
A complexidade do algoritmo descrito é O(n^4 log n). Isso ocorre porque o algoritmo possui um loop externo que se repete n vezes, um loop interno que se repete j vezes (onde j é uma potência de 2) e uma operação elementar dentro desse loop interno. Portanto, a complexidade é determinada pela multiplicação desses fatores: O(n * j * log n) = O(n * 2^k * log n) = O(n^4 log n).
Faça como milhares de estudantes: teste grátis o Passei Direto
Esse e outros conteúdos desbloqueados
16 milhões de materiais de várias disciplinas
Impressão de materiais
Agora você pode testar o
Passei Direto grátis
✏️ Responder
Para escrever sua resposta aqui, entre ou crie uma conta
Outros materiais
Perguntas relacionadas
Materiais relacionados
Compartilhar