Método de árvore de recursão

Para calcular o custo assintótico do Quicksort com diferentes divisões de subproblemas, utilizamos o método da árvore de recursão. O custo geral do algoritmo é dado pela fórmula:

T(n)=T(a?n)+T(b?n)+c?nT(n) = T(a \cdot n) + T(b \cdot n) + c \cdot n

Onde:

• aa e bb representam as proporções em que o vetor é dividido.
• c?nc \cdot n é o custo do particionamento no nível atual.

O objetivo é determinar o custo total T(n)T(n) analisando a profundidade da árvore de recursão e o custo em cada nível.

a) Divisão: 1/31/3 e 2/32/3

T(n)=T(n/3)+T(2n/3)+c?nT(n) = T(n/3) + T(2n/3) + c \cdot n

1. Número de subproblemas: Dois subproblemas (n/3n/3 e 2n/32n/3).
2. Altura da árvore: O vetor diminui em cada nível por um fator proporcional, até restar 1 elemento. A altura é log?3/2(n)\log_{3/2}(n).
3. Custo em cada nível: O custo total do particionamento em cada nível é linear, c?nc \cdot n.
4. Soma dos custos: A soma do custo em todos os níveis é dominada pelo custo no nível superior.

Custo final: O(nlog?n)O(n \log n).

b) Divisão: 1/91/9 e 2/102/10

T(n)=T(n/9)+T(2n/10)+c?nT(n) = T(n/9) + T(2n/10) + c \cdot n

1. Número de subproblemas: Dois subproblemas (n/9n/9 e 2n/102n/10).
2. Altura da árvore: O vetor diminui mais rapidamente do que no caso anterior. A altura é log?10/9(n)\log_{10/9}(n).
3. Custo em cada nível: O custo do particionamento permanece c?nc \cdot n.
4. Soma dos custos: A redução mais acentuada nos subproblemas mantém o custo assintótico geral.

Custo final: O(nlog?n)O(n \log n).

c) Divisão: 11 e (n?1)(n - 1)

T(n)=T(1)+T(n?1)+c?nT(n) = T(1) + T(n-1) + c \cdot n

1. Número de subproblemas: Um subproblema é constante (T(1)T(1)), e o outro é quase do mesmo tamanho (n?1n-1).
2. Altura da árvore: A árvore tem altura máxima, nn, pois cada partição reduz apenas um elemento por nível.
3. Custo em cada nível: O custo do particionamento em cada nível é c?nc \cdot n.
4. Soma dos custos: A soma é proporcional à altura da árvore.

Custo final: O(n2)O(n^2).

Resumo dos Custos Assintóticos

O algoritmo Quicksort utiliza a estratégia de dividir para conquistar, em que o vetor é dividido em duas partes de acordo com um pivô escolhido, e então cada uma dessas partes é ordenada recursivamente. O custo assintótico do Quicksort depende do pivô escolhido e da divisão do vetor em partes iguais ou desiguais.

a) Neste caso, a divisão do vetor é desigual, com 1/3 dos elementos menores ou iguais ao pivô e 2/3 dos elementos maiores ou iguais ao pivô. O custo assintótico do Quicksort pode ser representado por uma árvore de recursão balanceada, com altura log_3/2(n), em que n é o tamanho do vetor. O custo total é dado pela soma dos custos de cada nível da árvore, que é O(n).

b) Neste caso, a divisão do vetor também é desigual, com 1/9 dos elementos menores ou iguais ao pivô e 2/3 dos elementos maiores ou iguais ao pivô. O custo assintótico do Quicksort pode ser representado por uma árvore de recursão desbalanceada, com altura n/9, em que n é o tamanho do vetor. O custo total é dado pela soma dos custos de cada nível da árvore, que é O(n^2).

c) Neste caso, a divisão do vetor é igual, com apenas um elemento menor ou igual ao pivô e os demais maiores ou iguais ao pivô. O custo assintótico do Quicksort pode ser representado por uma árvore de recursão desbalanceada, com altura n, em que n é o tamanho do vetor. O custo total é dado pela soma dos custos de cada nível da árvore, que é O(n^2).