Questão 2876656

• 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

Considerando os algoritmos de ordenação por comparação, o limite inferior para o pior caso desses algoritmos é

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

Gabarito: C

Comentários

• Esse gabarito está correto? Para mim, ordenação por comparação/troca são Bubble sort(ou ordenação por flutuação), Comb sort(melhoria do Bubble sort), Cocktail sort(Bubble em duas direções) que no pior caso são Ω(n lg n).

  Alguém poderia comentar?

• Pior caso aí  Ω(n²) e não Ω(n lg n).

• Também fui na mesma linha de raciocinio dos colegas, porém a questão é copia e cola do Livro: Algoritmos. Teoria e Prática - Thomas Cormen;

  " Pior caso de um algoritmo de ordenação é o maior caminho da raiz até uma folha; ou seja, a altura da árvore

  .....

  Qualquer arvore de decisão para ordenar n elementos tem altura Ω(n lg n)."

  GABARITO, CORRETO, ALTERNATIVA C

• "o limite inferior" a sacada está nessa parte, pois quer saber dentre os algoritmos de ordenação, qual deles possui "o melhor caso" da notação Big-O (pior caso do algoritmo).

• Força Guerreiro!!!!!!