A pesquisa de dados envolve a determinação da chave pesquisa...

A alternativa CORRETA é a C.

A questão aborda algoritmos de pesquisa e classificação, importantes em computação para a organização e busca eficiente de dados. É necessário compreender as complexidades de tempo desses algoritmos e seu comportamento em diferentes casos.

Vamos analisar cada afirmativa:

I. Diz-se que o algoritmo O(log n) tem um tempo de execução linear.

Esta afirmativa está INCORRETA. O tempo de execução linear é representado por O(n). Um algoritmo com complexidade O(log n) é considerado mais eficiente do que um algoritmo linear, pois seu tempo de execução cresce de forma logarítmica em relação ao tamanho da entrada.

II. A pesquisa binária executa em O(log n) vezes, pois cada passo remove metade dos elementos restantes.

Esta afirmativa está CORRETA. A pesquisa binária é um algoritmo eficiente para encontrar um elemento em um vetor ordenado, reduzindo pela metade o número de elementos a cada iteração, resultando em uma complexidade de O(log n).

III. O algoritmo de classificação por inserção executa no tempo O(n²), no pior caso e no caso médio.

Esta afirmativa está INCORRETA. Embora o pior caso do algoritmo de inserção seja realmente O(n²), o caso médio pode variar e, em algumas situações, pode ser mais eficiente, principalmente se o conjunto de dados já estiver parcialmente ordenado.

IV. No pior caso, a primeira chamada à classificação por intercalação tem de fazer O(n) comparações para preencher os n slots no array final.

Esta afirmativa está CORRETA. No algoritmo de intercalação (merge sort), a fase de intercalação de duas sublistas ordenadas em uma lista final requer O(n) comparações para preencher os n slots, fazendo com que esta afirmativa seja precisa.

Em resumo, as afirmativas II e IV estão corretas, o que justifica que a alternativa correta seja a C.

Pra mim, o gabarito deveria ser B.

IV- classificação por intercalação é o mesmo que MergeSort. Logo deveria ser O(nlogn) para preencher os slots do array final.

Alguém comenta?

Letra Correta B)

Algoritmos por inserção é somente o "Insertion Sort" que possui complexidade 

Melhor Caso O(n) 

Caso Médio O(n²) 

Pior Caso O(n²)

Também acredito, quanto ao III não tenho dúvidas.

Quanto ao IV acredito que ele se refira a primeira chamada à classificação por intercalação, ou seja o passo de combinar.

O algoritmo tem duas fases. Primeiro se quebra o array recursivamente em n arrays de um elemento,

Depois começa-se a intercalação em um laço recursivo. Cada um desses laços vai fazer n comparações e como a cada passo teremos arrays com o dobro de tamanho, ordenada, esse laço precisará ser executado executado log2(n) vezes. Daí a complexidade n*log2(n).

Foi isso que tinha entendido, embora falta clareza ao item.

https://upload.wikimedia.org/wikipedia/commons/c/cc/Merge-sort-example-300px.gif

Tempo logarítmico O(log n) Busca binária

Tempo linear O(n)  Procurando o menor item em um array não ordenado

Tempo quadrático O(n2)  Bubble sort; Insertion sort

Insertion sort algoritmo de classificação por inserção:

                                                                        complexidade pior caso O(n2)

                                                                        complexidade caso médio O(n2)

                                                                        complexidade melhor caso O(n)

Resposta da banca ao recurso:

Recurso Improcedente. Ratifica-se a opção divulgada no gabarito preliminar. A banca mantém o gabarito divulgado anteriormente. (Gab. C)

I) Diz-se que o algoritmo 0(n) tem um tempo de execução linear.

III) O algoritmo de classificação por seleção executa no tempo 0(n²).

Fonte: DEITEL, P.; DEITEL, H. – Java: como programar – 8ª ed. São Paulo: Person Prentice Hall, 2010 – pág.: 633.

Gab. Final: C

Banca doida... =P