Número: 040
Enunciado:
Vimos que existe um algoritmo para comparar sequências similares. Esse algoritmo tenta se manter na diagonal principal da matriz de similaridade com uma tolerância k. Sabemos que, caso as sequências não sejam similares, o algoritmo também vai encontrar a resposta correta. Supondo que o valor inicial de k é 1 e que este valor é dobrado após cada 'rodada', qual das alternativas abaixo melhor reflete o número de 'rodadas' do algoritmo necessárias para encontrar a solução ótima no pior caso ? Suponha que as duas sequências têm tamanho n.
- n / 2
- n / 4
- log 2 n
- log 4 n
- NDA
Como o valor de K é dobrado a cada rodada, temos a seguinte sequência:
ResponderExcluir1 = 2^0 -> rodada 1
2 = 2^1 -> rodada 2
4 = 2^2 -> rodada 3
.
.
.
Kr = 2^r -> rodada R [Eq. 1],
onde Kr é o valor de K na última rodada R
R = (r + 1) [Eq. 2].
No pior caso o valor de Kr é aquele em que a matriz é inteiramente percorrida, ou seja,
Kr = n [Eq. 3]
Utilizando as equações Eq. 1 e Eq. 3 chegamos a
2^r = n [Eq. 4]
Aplicando o logaritmo na base 2 (log2) em ambos os lados da Eq. 4 obtemos
r = log2(n) [Eq. 5],
e o número de rodadas R (Eq. 2) para o pior caso fica
R = log2 (n) + 1 [Eq. 6]
Portanto, a alternativa que melhor reflete o número de rodadas R é a alternativa C.
Boa análise! Muito clara.
ResponderExcluir