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(n44log(n))
O(n33)
O(n22log22(n))
O(n55)
O(n33log(n))
Respondido em 11/04/2023 10:15:24
Explicação:
Vamos analisar o código simplif icado 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 é n 4log n
O(n44log(n))
O(n33)
O(n22log22(n))
O(n55)
O(n33log(n))
Calcule a complexidade do algoritmo, sabendo que a função f tem complexidade igual a O(n22).
O(n44log(n))
O(n33)
O(n22log22(n))
O(n55)
O(n33log(n))
Respondido em 11/04/2023 10:15:24
Explicação:
Vamos analisar o código simplif icado 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 é n 4log n
O(n44log(n))
O(n33)
O(n22log22(n))
O(n55)
O(n33log(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 função f que possui complexidade O(n^2). Portanto, a complexidade total é determinada pela multiplicação desses fatores: O(n * j * f) = O(n * 2^k * n^2) = O(n^4 * 2^k). Como k é igual a log(n), a complexidade final é 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