1. [POSCOMP] Considerando seu conhecimento sobre os algoritmos de ordenação, julgue as alternativas a seguir:
    a. Seja A[1, n] um vetor não ordenado de inteiros com um número constante k de valores distintos. Então existe um algoritmo de ordenação por contagem que ordena A em tempo linear.
    b. Seja A[1, n] um vetor não ordenado de inteiros com um número constante k 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 A[1, n] 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 k de valores distintos. Então o problema de ordenar A tem limite inferior O(n).
    d. Seja A[1, n] um vetor não ordenado de inteiros, cada inteiro com no máximo d dígitos, onde cada dígito assume um valor entre \mathrm{O}(\mathrm{n}) valores distintos. Então o problema de ordenar A tem limite inferior O(n lg n).
    e. Seja A[1, n] um vetor não ordenado de inteiros com um número constante k de valores distintos, então um um algoritmo de ordenação por comparação ótimo para ordenar A tem complexidade \mathrm{O}(\mathrm{n} \lg \mathrm{n})

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 A[1,n] um vetor não ordenado de inteiros com um número constante k de valores distintos. Então existe um algoritmo de ordenação por contagem que ordena A em tempo linear.”
O counting sort funciona em tempo \Theta(n + k). Se k é constante, então \Theta(n + k)=\Theta(n), ou seja, linear. Logo, (a) é verdadeira.

Passo 3

Alternativa (b): “Seja A[1,n] um vetor não ordenado de inteiros com um número constante k 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).”
O limite inferior para ordenação por comparações é \Omega(\log P), onde P é o número de permutações possíveis. Aqui P=k^n, pois cada posição tem k opções. Logo \log P=n\log k=\Theta(n). O limite inferior correto é \Omega(n), não \Omega(n\log n). Assim, (b) é falsa.

Passo 4

Alternativa (c): “Seja A[1,n] um vetor de inteiros com no máximo d dígitos, cada dígito em um conjunto de tamanho constante k. Então o problema de ordenar A tem limite inferior O(n).”
Qualquer algoritmo precisa ler todos os n itens, logo não pode ser mais rápido que \Omega(n). Em notação de limite inferior costuma-se escrever \Omega(n), mas dizer “limite inferior O(n)” significa que não é possível fazer melhor que ordem linear. Portanto, a ideia está correta: (c) é verdadeira.

Passo 5

Alternativa (d): “Seja A[1,n] um vetor de inteiros com no máximo d dígitos, cada dígito assume \mathcal{O}(n) valores. Então o problema de ordenar A tem limite inferior O(n\lg n).”
Se cada dígito tem \mathcal{O}(n) valores, o total de valores possíveis é \Theta(n^d). O limite inferior por comparações seria \Omega(n\log(n^d))=\Omega(d\,n\log n). Se d é constante, isso dá \Omega(n\log n), mas o enunciado diz “limite inferior O(n\lg n)” de modo genérico e não assume d constante. Além disso, existe ordenação por radix sort em \Theta(d\,n), que para d constante é linear. Logo a afirmação de limite inferior \Omega(n\log n) não se sustenta em geral. (d) é falsa.

Passo 6

Alternativa (e): “Seja A[1,n] um vetor não ordenado de inteiros com um número constante k de valores distintos, então um algoritmo de ordenação por comparação ótimo para ordenar A tem complexidade O(n\lg n).”
Um algoritmo ótimo por comparação deve usar pelo menos \Omega(n\log k) comparações, pois há k^n permutações, dando \log(k^n)=n\log k. Como k é constante, isso é \Theta(n). Logo um algoritmo ótimo roda em \Theta(n), não em \Theta(n\log n). Portanto, (e) é falsa.

Resposta

a. Verdadeira
b. Falsa
c. Verdadeira
d. Falsa
e. Falsa

Exercícios relacionados