MO417 - Questão para a prova oral
Número:Enunciado: Dada uma arvore de decisão de um algoritmo de ordenação por comparação, sabemos que dentre seus ramos ela tem um cujo tamanho é nlg(n), de onde vem a prova de que todo algoritmo por comparação é Ω(nlg(n)) para seu pior caso, porém alguns algoritmos como o insertionsort para o pior caso é O(n^2).
Dentro da perspectiva de arvore de decisão e do algorítmo insertion sort, é incorreto afirmar que:
- Assumimos a hipotese de que n! é o número de folhas mínimo de uma arvore de decisão para provarmos que todo algoritmo de comparação é Ω(nlg(n)).
- Devido a assumirmos a hipótese de que no "melhor" dos piores casos somente existirá uma comparação entre dois locus distintos da array para a prova de que todo algoritmo de comparação é Ω(nlg(n)).
- Devido ao insertion-sort fazer mais de uma comparação entre dois Locus distintos de um array, isso permite que ele passe do número de O(nlog(n)) e varie entre Ω(nlg(n)) e O(n^2) no seu pior caso.
- Devido ao insertion-sort fazer no pior caso a comparação de um elemento i qualquer com seus i-1 elementos anteriores para seus n elementos.
- NDA
