Questão 1208251

• Banca: CESPE / CEBRASPE
• Órgão: TJ-SE
• Ano: 2014
• Provas: CESPE - 2014 - TJ-SE - Analista Judiciário - Análise de Sistemas
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Complexidade de Algoritmos

        Um sistema de controle distribui os processos para os juízes de um tribunal utilizando critérios de prioridade associados a cada processo, de modo que novos processos podem ser analisados pelos juízes enquanto outros aguardam análise.

Considerando essas informações, julgue os itens a seguir, acerca dos tipos básicos de estruturas de dados e de operações sobre estruturas de dados.

Caso a implementação seja realizada por meio de max-heap, a operação de remoção de processos de maior prioridade levará um tempo de ordem O(log n).

• C. Certo
• E. Errado

Gabarito: C

Comentários

• puro chute essa... alguma explicação?

• O consumo de tempo do algoritmo é proporcionalao número de iterações do bloco de linhas 3 a 9. Para calcular esse número,examine a sequência de valores da variável j. No pior caso, j assume os valores i, 2i, 4i,…, 2^ki, … continuando enquanto tivermos 2^ki ≤ n. O maior valor de k nessa sequência será lg (n/i). Portanto,o número de iterações será lg (n/i) no pior caso e o consumo total de tempo será Ο(lg(n/i))

  Portanto,o consumo de tempo no pior caso é proporcional à alturado nó i na árvore.Se i = 1, por exemplo, o consumo de tempo é Ο(lg n). Se i = 2, o consumo também é Ο(lg n). Se i é maior que n/2,o consumo também é constante(ou seja, não depende de n nem de i).
  

  
  

  http://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/heap.html
  

• Heap é algoritmo de ordenação que imita uma arvora binária em forma de array. Como a busca em uma arvora binária a ordem é logarítmica, no heap tb vai ser.
• a complexidade do heapsort é igual a do mergesort -> log n em todos os casos 

• Força Guerreiro!!!!!!