Complexidade do Quicksort

Prévia do material em texto

Complexidade do Quicksort
Parâmetros: entrada particular + seleção do Pivô
Se o pivô sempre particiona a seqüência em 2 partes iguais então a relação de recorrência é:
T(n) = 2T(n/2) + O(n) , T(2) = 1
 (
(número de comparações)
Neste caso, já sabemos (mergesort) que T(n) = O (nlogn).
Pergunta: Conseguimos um tempo de execução O(nlogn) sob hipóteses mais fracas?
R: Sim.
Antes de mostrarmos este fato, observe o seguinte:
Se o pivô é muito próximo de um lado da seqüência, então o tempo de execução é alto.
Por exemplo, se o pivô é o menor elemento da seqüência então
A primeira partição exige (n-1) comparações e coloca apenas o pivô no local certo.
Se a seqüência já está em ordem crescente e sempre selecionamos o primeiro elto como pivô então 
	T(n) = n-1 + n-2 + ... + 1 ( n + n-1 + n-2 + ... + 1 = n(n+1)/2 = O(n2) 
Pior caso do Quicksort: Seqüências ordenadas ou quase ordenadas.
 Podemos evitar o pior caso quadrático:
-mediana(primeiro,meio,último) ( significa escolher o segundo maior elemento.
-random(esquerda,direita)
Atenção: O tempo do quicksort ainda será O(n2) no pior caso. 
Por que?
R: Existe a chance de que o pivô seja o menor elemento na seqüência.
Porém...
 A probabilidade deste fato ocorrer é muito pequena!!
Vamos analisar este caso
Assumiremos que cada elemento xi tem a mesma probabilidade de ser selecionado como o pivô.
O tempo de execução do quicksort se o i-ésimo elto é o pivô deve ser escrito como:
T(n) = (n-1) + T (i-1) + T(n-i)
OBS: Para prosseguir nos cálculos, usaremos os conceitos de variável randômica, valor esperado ou esperança,
E(x) = ∑ x Pr(X=x)
 x
Se cada elemento tem a mesma probabilidade de ser selecionado (equiprovável), então o tempo medio é:
		 n 
T(n) = (n-1) + 1/n ∑ (T(i-1) + T(n-i)) 
		 i=1
 n n
 = (n-1) + 1/n ∑T(i-1) + 1/n∑T(n-i)
 i=1 i=1
 (n-1)
 = (n-1) + 2/n ∑ T(i)
	 i=0
Como resolver esta relação de recorrência? (seção 3.5.3, p. 52/53, livro do Manber)
 			 n-1
(*) T(n) = (n-1) + 2/n ∑ T(i) (para n>= 2) , T(1) = 0
			 i=1
1º passo: Desejamos cancelar alguns dos termos T(i). Para isto, vamos analisar a expressão correspondente para o valor (n + 1)
				 n
(**) T(n+1) = (n+1) - 1 + 2/(n+1) ∑ T(i) (n>=2) 
			 i=1
Por conveniência, multiplicaremos ambos os lados por “n” em (*) e por (n+1) em (**). Temos então,
			 n-1
(1) n T(n) = n (n-1) + 2 ∑ T(i) (n>=2)
			 i=1
 n 
(2) (n+1) T(n+1) = (n+1) n + 2 ∑T(i) (n>=2)
				 i=1	
Agora, subtraindo (1) de (2) obtemos:
(n+1)T(n+1) - nT(n) = (n+1)n – n(n-1) + 2T(n) = 
 = 2n + 2T(n) , (n>=2)
Isto implica que,
(n+1)T(n+1) = 2n + 2T(n) + nT(n) = 2n + (n+2)T(n)
T(n+1) = 2n/(n+1) + (n+2)/(n+1) T(n) ( 2 + (n+2)/(n+1) T(n)
Reescrevendo para T(n) temos:
T(n) = 2 + (n+1)/n T(n-1)
Se expandirmos esta fórmula, chegamos a seguinte expressão:
T(n) = 2 (n+1) (1/(n+1) + 1/n + 1/(n-1) + ... + 1/3)
= 2 (n+1) (H(n+1) – 1.5), onde H(n) = 1 + 1/2 + 1/3 + ... + 1/n é a serie harmônica.
Não iremos provar aqui mas a seguinte igualdade é válida (livro do Cormen)
 H(n) = ln n + γ + O(1/n) onde γ = 0,577 é a constante de Euler.
 Logo,
 T(n) <= 2 (n+1) (ln n + γ – 1.5) + O(1) = O (nlogn)
 C.Q.D
			 
LIMITE INFERIOR PARA ORDENAÇÂO
Começamos com um algoritmo O(n2) e melhoramos para um algoritmo O(nlogn).
É possível melhorar??
R: Não
Definição(limite inferior para um problema) : Um limite inferior para o problema é uma prova de que nenhum algoritmo pode resolvê-lo melhor.
Atenção: Necessitamos escolher um modelo que corresponda a um algoritmo arbitrário e provar que o tempo de execução de qualquer algoritmo que siga o modelo deve ser ( do que o limite inferior.
Nosso modelo : Árvores de decisão
Por que?
R: Árvores de decisão modelam computações que consistem principalmente em comparações.
Definição(árvore de decisão) : árvore de decisão são árvores binárias onde cada vértice interno é associado com uma consulta cuja resposta é uma de duas possibilidades, cada uma delas associada a uma ramificação. Cada folha é associada com uma saída possível. 
Exemplo:
 T
Árvore de decisão 
 
O pior caso do tempo de execução está associado com a altura da árvore T, a qual é o nº máximo de consultas exigidas por uma entrada.
Teorema: Todo algoritmo baseado em árvore de decisão para ordenação tem altura Ω(nlogn).
Prova: A entrada para ordenação é uma seqüência x1,x2,...,xn. A saída é a mesma seqüência ordenada. Outra maneira de olhar a saída é como uma permutação da entrada.
Cada permutação é uma saída possível, visto que a entrada pode estar em qualquer ordem. Um algoritmo de ordenação está correto, se ele trata todas as entradas possíveis. 
Logo, cada permutação de (1,2,...,n) devera ser representada como uma saída possível na árvore de decisão para ordenação. As saídas são associadas com as folhas, como temos n! permutações de n eltos e como a árvore é binária concluímos que a altura da árvore é pelo menos log2(n!).
Pela formula de Stirling (livro do Cormen):
 ____
n! = √ 2πn (n/e)n (1 + O(1/n))
Desta forma,
log2(n!) = Ω(nlogn). (+)
Cálculo (esboço para (+)): log2(n!) ( log(2πn)1/2 + log(n/e)n (
	 ( ½ logn + n (logn) – loge) ( C1 nlogn