(Questão 05-06 pontos)

Para o método de ordenação Quicksort o seu pior caso ocorre quando cada partição divide o arquivo em uma parte de tamanho n-1 e outra parte de tamanho 1 .
T(n)=T(n-1)+n-1
Em contrapartida, o melhor caso ocorre quando cada partição divide o arquivo em duas partes iguais.
T(n)=2 T(n / 2)+n-1
Mostre, a partir da resolução das equações de recorrência, qual a ordem de complexidade para cada um dos casos.

Passo 1

O enunciado trata do Quicksort e dá duas recorrências: no pior caso
T(n)=T(n-1)+(n-1)
e no melhor caso
T(n)=2,Tl(n/2r)+(n-1)
Vamos resolver cada uma para determinar a ordem de crescimento.

Passo 2

Para o pior caso, use expansão (ou somatório). Suponha T(1)=Theta(1). Expandindo até T(1):
T(n)=T(n-1)+(n-1)=T(n-2)+(n-2)+(n-1)=cdots=T(1)+sumj=1^n-1j
Como
sumj=1^n-1j=(n-1)n2=Theta(n^2),
concluímos
T(n)=Theta(n^2)

Passo 3

Para o melhor caso, aplicamos o Teorema Mestre à recorrência
T(n)=2,Tl(n/2r)+(n-1)
Aqui a=2, b=2 e f(n)=n-1=Theta(n). Como n^logba=n^log2 2=n e f(n)=Thetal(n^logbar), estamos no caso 2 do Mestre, que dá
T(n)=Thetal(nlog nr)

Resposta

Pior caso: Theta(n^2)
Melhor caso: Theta(nlog n)

Exercícios relacionados