Considere a função abaixo, retirada integralmente do texto anexo, e as constantes TAMANHO space QUENTE equals 5 space 000 straight e TAMANHO_TOTAL equ

Question

Considere a função abaixo, retirada integralmente do texto anexo, e as constantes TAMANHO space QUENTE equals 5 space 000 straight e TAMANHO_TOTAL equals 100 straight _ 000. def space localizar_produto left parenthesis sku_busca colon space int comma space space space space space space space space space space space space space space space space space space space space space space space space space space space space space space space space space space space space cache colon space List left square bracket Produto right square bracket comma space space space space space space space space space space space space space space space space space space space space space space space space space space space space space space space space space space space space catalogo_ordenado colon space List left square bracket Produto right square bracket right parenthesis space minus greater than space Dict colon space space space space space straight t 0 space equals space time. perf minus counter left parenthesis right parenthesis space space space space space res_cache space equals space pesquisa_linear left parenthesis cache comma space sku_busca right parenthesis space space space space space if space res_cache left square bracket " escontrado " right square bracket colon space space space space space space space space space res_cache left square bracket " fonte " right square bracket space equals space " cache " space space space space space space space space space res_cache left square bracket " tempo_ms " right square bracket space equals space left parenthesis time. perf_counter left parenthesis right parenthesis space minus space straight t 0 space asterisk times space 1000 space space space space space space space space space return space res_cache space space space space res_full space equals space pesquisa_binaria left parenthesis catalago_ordenado comma space sku_busca right parenthesis space space space space res_full left square bracket " fonte " right square bracket space equals space " catálago " space space space space res_full left square bracket " tempo_ms " right square bracket space equals space left parenthesis time. perf_counter left parenthesis right parenthesis space minus space straight t 0 space asterisk times space 1000 space space space space return space res_full Se o SKU procurado estiver presente somente na posição final do cache (índice 4 999), qual será o número exato de comparações realizadas pelo algoritmo? a. 1 b. ⌈log₂ 5 000⌉ c. 5 000 d. ⌈log₂ 100 000⌉ e. 5 000 + ⌈log₂ 100 000⌉

Ed · Answer

Para resolver essa questão, precisamos entender como funcionam os algoritmos de busca linear e binária.

1. **Busca Linear**: Este algoritmo percorre todos os elementos da lista até encontrar o elemento desejado. Se o SKU procurado estiver na última posição do cache (índice 4.999), o algoritmo fará 5.000 comparações, pois ele precisa verificar cada elemento até chegar ao último.

2. **Busca Binária**: Este algoritmo é mais eficiente, mas requer que a lista esteja ordenada. Ele divide a lista em duas partes a cada iteração. O número de comparações necessárias para encontrar um elemento em uma lista de tamanho $ n $ é dado por $ \lceil \log_2 n \rceil $.

Agora, analisando as opções:

a. 1 - Isso não é correto, pois o SKU está na última posição, então não seria encontrado na primeira comparação.

b. $ \lceil \log_2 5.000 \rceil $ - Isso se refere ao número de comparações na busca binária, mas não é o que estamos procurando, já que a busca linear é a que faz 5.000 comparações.

c. 5.000 - Esta é a quantidade de comparações feitas pela busca linear, que é o que estamos buscando.

d. $ \lceil \log_2 100.000 \rceil $ - Isso se refere à busca binária em uma lista de 100.000 elementos, mas não é relevante para a busca no cache.

e. $ 5.000 + \lceil \log_2 100.000 \rceil $ - Isso combina a busca linear e a binária, mas não é o que estamos buscando.

Portanto, a resposta correta é: **c. 5.000**.

Orçamento Público

Respostas

Ainda com dúvidas?

Mais conteúdos dessa disciplina