Questão 606163

• Banca: CESGRANRIO
• Órgão: FINEP
• Ano: 2011
• Provas: CESGRANRIO - 2011 - FINEP - Analista - Desenvolvimento de Sistemas
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Algoritmos de Ordenação; Complexidade de Algoritmos

Considerando-se a análise assintótica (Notação Big O), qual é a complexidade do caso médio do algoritmo de ordenação chamado de Ordenação por Inserção?

• A. O(n²)
• B. O(1)
• C. O(n)
• D. O(n log n)
• E. O(log n)

Gabarito: A

Comentários

• Questão classificada erroneamente.
• Detalhes: http://pt.wikipedia.org/wiki/Insertion_sort
  
  Complexidade do caso médio do Insertion Sort (algoritmo de Ordenação por Inserção = O(n²)
  
  Insertion sort, ou ordenação por inserção, é um simples algoritmo de ordenação, eficiente quando aplicado a um pequeno número de elementos. Em termos gerais, ele percorre um vetor de elementos da esquerda para a direita e à medida que avança vai deixando os elementos mais à esquerda ordenados. O algoritmo de inserção funciona da mesma maneira com que muitas pessoas ordenam cartas em um jogo de baralho como o pôquer.

• A complexidade de tempo do caso médio é igual a do pior caso. Lembrando que a Complexidade temporal de um algoritmo se dá em função do tamanho (n) da entrada. 

  Já a Ordenação por Partição é O(n log n). 

  
  

• Questão errada. Cabe recurso.

• Gabarito A

  INSERÇÃO DIRETA ---> complexidade pior n2 e complexidade melhor n.

   

   

   

  "Retroceder Nunca Render-se Jamais !"
  Força e Fé !
  Fortuna Audaces Sequitur !

• algo____________best___________average___________worst

  Quicksort   Ω(n log(n))___________   Θ(n log(n))___________   O(n^2)   

  Mergesort   Ω(n log(n)) ___________  Θ(n log(n)) ___________  O(n log(n))   

  Timsort   Ω(n) ___________  Θ(n log(n)) ___________  O(n log(n))   

  Heapsort   Ω(n log(n))___________   Θ(n log(n)) ___________  O(n log(n))

  Bubble Sort   Ω(n) ___________  Θ(n^2)  ___________ O(n^2)

  Insertion Sort   Ω(n) ___________  Θ(n^2)  ___________ O(n^2)

  Selection Sort   Ω(n^2) ___________  Θ(n^2)  ___________ O(n^2)

  Tree Sort   Ω(n log(n))  ___________ Θ(n log(n))  ___________ O(n^2)

  Shell Sort   Ω(n log(n))  ___________ Θ(n(log(n))^2)  ___________ O(n(log(n))^2)

  Bucket Sort   Ω(n+k)  ___________ Θ(n+k)  ___________ O(n^2)

  Radix Sort   Ω(nk)  ___________ Θ(nk)  ___________ O(nk)

  Counting Sort   Ω(n+k)  ___________ Θ(n+k)  ___________ O(n+k)

  Cubesort   Ω(n)   ___________Θ(n log(n))  ___________ O(n log(n))