Questão Q304420

Question

Dispõe-se de uma tabela contendo os dados de 5.000 inscritos num concurso público. A tabela está rigorosamente classificada em ordem alfabética crescente do nome completo do candidato e também já se verificou que não há homônimos inscritos no concurso. Deseja-se localizar um candidato na tabela a partir de seu nome completo usando a técnica de Pesquisa Binária (Binary Search). Qual é o número máximo de incursões à tabela para localizar o candidato procurado (ou descobrir que ele não existe)?

Answer

Muito bem pessoal,
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 = Log₂^N(logarítmo de N na base 2), ou então 2^{max_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,
2¹⁰ = 1024
2¹¹ = 2048
2¹² = 4096
2¹³ = 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.

Answer

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

Answer

Força Guerreiro!!!!!!

SóProvas

Continue usando...

O que está incluso