Análise da Questão de Complexidade Algorítmica
Vamos analisar este problema passo a passo para determinar a complexidade do algoritmo.
Entendendo o Problema
O programa tem duas estruturas principais:
- Loop externo: Percorre uma lista com 10 elementos (valor constante)
- Loop interno: Para cada elemento
n, calcula a soma: n + n/2 + n/4 + n/8 + ... + n/n
Analisando o Loop Interno
Como todos os elementos são potências de 2 maiores que 4, temos:
- Elementos possíveis: 8, 16, 32, 64, 128, 256, ...
- Ou seja: n = 2^k onde k \geq 3
A série de divisão por 2 até chegar em 1 tem aproximadamente log₂(n) termos:
| Valor de n | Número de Termos na Soma |
|---|
| 8 ($2^3$) | 4 termos |
| 16 ($2^4$) | 5 termos |
| 32 ($2^5$) | 6 termos |
| 64 ($2^6$) | 7 termos |
Isso nos mostra que o número de operações no loop interno é proporcional a $\log_2(n)$.
Calculando a Complexidade Total
Complexidade = (\text{Número de elementos}) \times (\text{Operações por elemento})
Complexidade = 10 \times O(\log n)
Como 10 é um valor constante, ele não afeta a notação Big-O:
O(10 \times \log n) = O(\log n)
Conclusão
Alternativa D - O(log n)
Resumo:
- O loop externo tem tamanho fixo (10 elementos) → O(1)
- O loop interno depende do valor de cada elemento → O(log n)
- Complexidade total: O(1) × O(log n) = O(log n)