Questão 1095952

• Banca: CAIP-IMES
• Órgão: Câmara Municipal de São Caetano do Sul - SP
• Ano: 2012
• Provas: CAIP-IMES - 2012 - Câmara Municipal de São Caetano do Sul - SP - Analista de Tecnologia da Informação
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Complexidade de Algoritmos

A complexidade de execução do algoritmo heapsort, no pior caso é:

• A.
• B. O(n log n).
• C. .
• D. O(n).

Gabarito: B

Comentários

• Tem um desempenho em tempo de execução muito bom em conjuntos ordenados aleatoriamente, tem um uso de memória bem comportado e o seu desempenho em pior cenário é praticamente igual ao desempenho em cenário médio. Alguns algoritmos de ordenação rápidos têm desempenhos espectacularmente ruins no pior cenário, quer em tempo de execução, quer no uso da memória. O Heapsort trabalha no lugar e o tempo de execução em pior cenário para ordenar n elementos é de O (n lg n). Lê-se logaritmo (ou log) de "n" na base 2. Para valores de n, razoavelmente grandes, o termo lg n é quase constante, de modo que o tempo de ordenação é quase linear com o número de itens a ordenar.

  
  

  http://pt.wikipedia.org/wiki/Heapsort
  

• Força Guerreiro!!!!!!