- [POSCOMP] Considerando seu conhecimento sobre os algoritmos de ordenação, julgue as alternativas a seguir:
a. Seja
um vetor não ordenado de inteiros com um número constante
de valores distintos. Então existe um algoritmo de ordenação por contagem que ordena A em tempo linear.
b. Seja
um vetor não ordenado de inteiros com um número constante
de valores distintos, então o limite inferior para um algoritmo de ordenação por comparações para ordenar A é de O(n lg n).
c. Seja
um vetor não ordenado de inteiros, cada inteiro com no máximo d dígitos, onde cada dígito assume um valor entre um número constante
de valores distintos. Então o problema de ordenar A tem limite inferior O(n).
d. Seja
um vetor não ordenado de inteiros, cada inteiro com no máximo d dígitos, onde cada dígito assume um valor entre
valores distintos. Então o problema de ordenar A tem limite inferior O(n lg n).
e. Seja
um vetor não ordenado de inteiros com um número constante
de valores distintos, então um um algoritmo de ordenação por comparação ótimo para ordenar A tem complexidade
a. Seja
b. Seja
c. Seja
d. Seja
e. Seja
Passo 1
O enunciado apresenta cinco afirmações sobre algoritmos de ordenação e pede que julguemos cada uma. O conteúdo envolve algoritmos não comparativos (counting sort e radix sort) e limites inferiores para algoritmos de ordenação por comparações.
Passo 2
Alternativa (a): “Seja
um vetor não ordenado de inteiros com um número constante
de valores distintos. Então existe um algoritmo de ordenação por contagem que ordena
em tempo linear.”
O counting sort funciona em tempo . Se
é constante, então
, ou seja, linear. Logo, (a) é verdadeira.
O counting sort funciona em tempo
Passo 3
Alternativa (b): “Seja
um vetor não ordenado de inteiros com um número constante
de valores distintos, então o limite inferior para um algoritmo de ordenação por comparações para ordenar
é de
.”
O limite inferior para ordenação por comparações é , onde
é o número de permutações possíveis. Aqui
, pois cada posição tem
opções. Logo
. O limite inferior correto é
, não
. Assim, (b) é falsa.
O limite inferior para ordenação por comparações é
Passo 4
Alternativa (c): “Seja
um vetor de inteiros com no máximo
dígitos, cada dígito em um conjunto de tamanho constante
. Então o problema de ordenar
tem limite inferior
.”
Qualquer algoritmo precisa ler todos os itens, logo não pode ser mais rápido que
. Em notação de limite inferior costuma-se escrever
, mas dizer “limite inferior
” significa que não é possível fazer melhor que ordem linear. Portanto, a ideia está correta: (c) é verdadeira.
Qualquer algoritmo precisa ler todos os
Passo 5
Alternativa (d): “Seja
um vetor de inteiros com no máximo
dígitos, cada dígito assume
valores. Então o problema de ordenar
tem limite inferior
.”
Se cada dígito tem valores, o total de valores possíveis é
. O limite inferior por comparações seria
. Se
é constante, isso dá
, mas o enunciado diz “limite inferior
” de modo genérico e não assume
constante. Além disso, existe ordenação por radix sort em
, que para
constante é linear. Logo a afirmação de limite inferior
não se sustenta em geral. (d) é falsa.
Se cada dígito tem
Passo 6
Alternativa (e): “Seja
um vetor não ordenado de inteiros com um número constante
de valores distintos, então um algoritmo de ordenação por comparação ótimo para ordenar
tem complexidade
.”
Um algoritmo ótimo por comparação deve usar pelo menos comparações, pois há
permutações, dando
. Como
é constante, isso é
. Logo um algoritmo ótimo roda em
, não em
. Portanto, (e) é falsa.
Um algoritmo ótimo por comparação deve usar pelo menos
Resposta
a. Verdadeira
b. Falsa
c. Verdadeira
d. Falsa
e. Falsa
b. Falsa
c. Verdadeira
d. Falsa
e. Falsa