Lista de exercicio 7 - Cormen 2º Edição

Prévia do material em texto

Aluno: Vinicius Barcelos Silva 
Matricula: 108251 
  
8.1​1  
A menor profundidade possivel será (n​1).  
  
8.2​3  
O COUNTING​SORT irá funcionar corretamente, não importa em que ordem A seja processada  
na entrada, no entanto, não é estável. A modificação do laço atual provoca números com o  
mesmo valor que aparecem na ordem inversa na saída.  
  
8.2​4  
Dado n inteiros de 1 a k mostram como contar o número de elementos de A para B com tempo  
O(1) e um tempo de pré​processamento O(n + k). Como mostrado no COUNTING​SORT  
podemos produzir uma matriz C de tal modo que C[i] contém o número de elementos menor do  
que ou iguais a i. Portanto, C[b] ​ C[a] dá a resposta desejada.  
  
8.3​2  
Insertion Sort e Merge Sort são algoritmos de ordenação estáveis. Considerando a  
estabilidade Quicksort depende da implementação e o Heap Sort não é estável.  
  
8.3​4  
O número de dígitos usados ​para representar um conjunto de n² números diferentes de um  
sistema k​ária é  . Assim, considerando os n² números como a raiz de n números  lg  (n²)d =   k   
temos que:    lg (n²)  2 lg (n)  2d =   n =   n =    
Então o radix sort terá um tempo de:   (d(n )) (2(n )) (n)Θ + k = Θ + n = Θ  
  
8.4​2  
Basta substituir o insertion sort usado para classificar as listas ligadas com algum algoritmo de  
ordenação com pior caso O(n lg n), por exemplo, o merge sort. A classificação, em seguida,  
leva tempo:  
 
 (n  lg n  )   (n  lg n)  (lg n)  (n  )  O (n lgn)  ∑
n−1
i=0
O i i ≤ ∑
n−1
i=0
O i = O ∑
n−1
i=0
O i =     
  
Portanto, o tempo total do bucket sort será O(n lg n).