1. Dado um array com números variando entre 1 até n^{6} ( n é o tamanho do array). É possível ordenar o array em tempo linear? Justifique sua resposta.

Passo 1

O enunciado dá um array A de tamanho n cujos elementos são inteiros no intervalo de 1 até n^{6}. Pergunta-se se é possível ordenar esse array em tempo \Theta(n). O conteúdo envolvido é algoritmos de ordenação de inteiros, em particular counting sort e radix sort, e o limite inferior para ordenação baseada apenas em comparações.

Passo 2

Se usássemos apenas comparações, há o limite inferior \Omega(n\log n) de comparações para ordenar n elementos, o que impede tempo linear. Logo, para alcançar \Theta(n) precisamos usar um algoritmo que aproveite o fato de os elementos serem inteiros em um intervalo conhecido.

Passo 3

O counting sort ordena n inteiros no intervalo [1,k] em tempo \Theta(n + k). Aqui teríamos k = n^{6}, logo o tempo seria
\Theta(n + n^{6}) = \Theta(n^{6}),
o que não é linear em n.

Passo 4

O radix sort resolve isso quebrando cada número em dígitos em uma base B e aplicando counting sort em cada dígito. Precisamos de
d = \bigl\lceil \log_{B}(n^{6})\bigr\rceil
dígitos. Se escolhermos B = n, então
d = \bigl\lceil \log_{n}(n^{6})\bigr\rceil = 6
e cada passo de counting sort leva \Theta(n + B) = \Theta(n + n) = \Theta(n). Como são d=6 passes, o tempo total é
\Theta\bigl(d\,(n+B)\bigr) = \Theta\bigl(6\cdot 2n\bigr) = \Theta(n).

Resposta

Sim. Basta usar radix sort com base B = n, em que cada um dos 6 passes de counting sort custa \Theta(n), resultando em ordenação em tempo \Theta(n).

Exercícios relacionados