Dispõe-se de uma tabela contendo os dados de 5.000 ...
Ao utilizarmos um algoritmo de Pesquisa Binária (Binary Search) em uma lista de dados ordenados, temos que o número máximo de iterações que deverão ocorrer até que o dado desejado seja encontrado, ou que se constate que ele não existe, é dado pela seguinte fórmula:
max_iterações = Log2N (logarítmo de N na base 2), ou então 2max_iterações = N (onde N é o número de registros contidos na lista de dados, que para a questão é de 5000).
Para facilitar a resolução, podemos adotar a seguinte estratégia: sabemos que,
210 = 1024
211 = 2048
212 = 4096
213 = 8192
Desta forma, com 12 iterações poderiamos encontrar um dado desejado em uma lista de no máximo 4096 elementos. Todavia, nossa lista é composta por 5000 elementos, o que exige no máximo 13 iterações. Lembrando que com 13 iterações poderiamos encontrar o dado desejado em uma lista com até 8192 elementos.
b-
complexidade do binary search tree é O(log n) (best case, ja ordenado) e O(n) (worst case).
formula: log2 (N)
e.g. log2 (1024) = 10 -> 2^10 = 1024
como o colega notou, sao necessarias 2^13 vezes para perfazer o total de um array de 5000 elementos. log2 (5000) é um numero decimal entre 12 e 13, mas arredonda-se para cima pq nao existe meia iteracao
Força Guerreiro!!!!!!
Alternativa correta: B
A questão aborda o uso da Pesquisa Binária para localizar um candidato em uma tabela de dados classificada em ordem alfabética. A Pesquisa Binária é um algoritmo eficiente para busca em listas ordenadas, reduzindo o intervalo de busca pela metade a cada comparação.
Para resolver a questão, precisamos calcular o número máximo de incursões (ou passos) necessários para encontrar um elemento em uma lista de 5.000 elementos usando a Pesquisa Binária. Este número é determinado pelo conceito de logaritmo na base 2.
A fórmula básica para determinar o número máximo de incursões é:
log2(n)
onde n é o número de elementos na lista. No caso, temos 5.000 inscritos. Então, precisamos calcular log2(5000).
Calculando, temos:
log2(5000) ≈ 12.29
Como o número de incursões deve ser um inteiro, arredondamos para cima, resultando em 13 incursões.
Portanto, a alternativa correta é a alternativa B - 13.
Vamos agora analisar as alternativas incorretas:
A - 12: Embora 12 seja um valor próximo, ao arredondar o logaritmo de 5000, obtemos 13, não 12. Portanto, esta alternativa está incorreta.
C - 500: Esta alternativa é muito maior que o valor correto. A Pesquisa Binária é muito mais eficiente, reduzindo drasticamente o número de comparações necessárias.
D - 2.500: Esta alternativa corresponde à metade do número total de elementos. No entanto, a Pesquisa Binária faz uso do logaritmo na base 2, o que resulta em um número de comparações muito menor.
E - 5.000: Esta alternativa sugere que todos os elementos teriam que ser verificados, o que corresponde a uma Pesquisa Linear, não à Pesquisa Binária. A Pesquisa Binária é muito mais eficiente, conforme explicado.
Essas explicações devem ajudar a entender melhor a abordagem da Pesquisa Binária e como calcular o número máximo de incursões necessárias para buscar um elemento em uma lista ordenada.