Questão 2876650

• Banca: FCM
• Órgão: IFN-MG
• Ano: 2018
• Provas: FCM - 2018 - IFN-MG - Ciências da Computação: Teoria da Computação
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Algoritmos de Ordenação

Para o método de ordenação Quicksort, a ordem de complexidade do pior caso e do caso médio, respectivamente, é

• A. θ(n² ) e θ(n² ).
• B. θ(n² ) e θ(n lg n ).
• C. θ(n lg n ) e θ(n² ).
• D. θ(n lg n ) e θ(n lg n ).
• E. θ(n lg n ) e θ(n).

Gabarito: B

Comentários

• Correto

  
  

  QuickSort:

  Pior n²

  Médio n*log n

  Melhor n*log n

• Gabarito B

  Complexidade

  MERGESORT ---> complexidade nlogn

  QUICKSORT ---> complexidade no pior caso n2 e complexidade no melhor caso nlogn

  BUBBLESORT ---> complexidade pior n2

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

  HEAPSORT ---> complexidade nlogn

  "Retroceder Nunca Render-se Jamais !"

  Força e Fé !

  Fortuna Audaces Sequitur !

• b-

  quicksort é normalmente (n long n). quando é pior caso, n².

• Força Guerreiro!!!!!!

• GABARITO B

  Quick Sort: Neste método, a lista é dividida em parte esquerda e parte direita, sendo que os elementos da parte esquerda são todos menores do que os elementos da parte direita. Em seguida, as duas partes são ordenadas recursivamente.

  • Ordenação rápida e eficiente;
  • Adota a estratégia de divisão-e-conquista;

      A estratégia consiste em rearranjar as chaves de modo que os menores precedem os maiores.

      Pivô: O primeiro da lista;

  • Melhor caso: O(n log n)
  • Médio caso: O(n log n)
  • Pior caso: O(n²)