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

Prévia do material em texto

Aluno: Vinícius Barcelos Silva
Matricula: 108251
Exercícios
2.1­3
Entrada: A = <ha1, a2, … an> e um valor v
Saída: O índice i, tal que v=A[i] ou null caso o valor não seja encontrado
for i 1 to n do
if A[i] = v then
return i
end if
end for
return null
2.2­1
/1000  100n    Θ (n  )n3 −   2+3 =   3
2.2­2
Entrada: A = <a1, a2, ... an>
Saída: Ordenado de A.
for i 1 to n ­ 1 do
j <­ FIND­MIN(A;i; n)
A[j] A[i]↔
end for
(n  )  Φ(∑ni=1 i) = Φ 2
Nesse caso vale tanto para o pior caso como para o melhor caso.
2.2­4
Tratando melhor os casos de entrada.
2.3­3
Base: n = 2, e temos n lgn = 2 lg 2 = 2 ∙ 1 = 2. 
Para o passo indutivo, a nossa hipótese indutiva é que T (n / 2) = (n / 2) lg (n / 2). 
Logo:
T(n) = 2T(n / 2) + n 
      = 2 (n / 2), lg (n / 2) + n 
 = N (LGN ­1) + n 
 = N LGN­n + n 
 = N lgn, 
2.3­4
Seguindo a recorrência temos para diferentes valores de  que:(n) Θ
T(n) =  (1)                     if  n Θ = 1
T(n) = T(n­1) +  (n)    if  nΘ > 1
Logo teremos a seguinte solucao de recorrência:    (n)  Θ(n  )T =   2
2.3­5
Busca Binaria Iterativa
while low ≤ high
do mid ←(min+max)/2
if v = A[meio]
then return meio
if v > A[mid]
then min ← meio +1
else max ← meio −1
return NULL
Aqui terminamos a busca quando nos seguintes casos: 
 ­ quando não temos sucesso na busca, ou seja, quando o intervalo é vazio (ou seja, Menor> Maior);
 ­ quando o valor v foi encontrado, sendo que v seria o elemento do meio pesquisado e a pesquisa continua 
com o intervalo reduzido pela metade.
Logo a recorrência para esse procedimento é, T (n) = T (n / 2) + (1), cuja solução sera T (n) = (Lg n).Θ Θ
2.3­6
Não, pois a busca binaria não teria um efeito sobre a movimentação dos elementos durante a realocação 
dos mesmos, logo a busca binaria sozinha não faria diferença no tempo de execução.