Gabarito disponível
Considere o código Python abaixo, projetado, hipoteticamente, para implementar uma função de hash aplicada no âmbito da segurança cibernética da Marinha do Brasil. Sabe-se que as complexidades em termos de tempo de execução de "func1", "func2" e "func3" são definidas com base no parâmetro único "N" de entrada de cada uma delas e são iguais, respectivamente, a O(N), O(N²) e O(N².log(N)). Assinale a opção com a correta complexidade global do código em função de "N".
import libtamandare as ltan
hash_final = 0
for i in range(0, N):
hash_final += ltan.func1(N, hash_final)
for j in range(i, N):
hash_final %= ltan.func2(N, hash_final)
iter = 1
while iter < N:
iter *= 3
hash_final -= ltan.func3(N, hash_final)
return hash_final
import libtamandare as ltan
hash_final = 0
for i in range(0, N):
hash_final += ltan.func1(N, hash_final)
for j in range(i, N):
hash_final %= ltan.func2(N, hash_final)
iter = 1
while iter < N:
iter *= 3
hash_final -= ltan.func3(N, hash_final)
return hash_final
Resolução comentada
O laço duplo com func2 domina a complexidade: O(N⁴).
O laço externo executa func1 N vezes, com custo total N·N = N². O laço interno executa cerca de N²/2 vezes uma func2 de custo O(N²), o que dá O(N⁴). O while executa log₃N vezes func3, com custo N²·log²N. O termo dominante é N⁴.
Análise das alternativas
A, B, C e D) Subestimam a complexidade, pois ignoram que o N²/2 chamadas de func2, cada uma O(N²), resultam em N⁴, que supera N³·log N e N²·log²N.
Referência: Análise de complexidade assintótica (Cormen et al.).
Resolução comentada do VaiConcursos.