Método de árvore de recursão

Professora Ilze O.

Identidade verificada

• CPF verificado
• E-mail verificado

Respondeu há 1 ano

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).