Lista de exercicio 2 Analise e Projeto de Algoritmos

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 n3/1000 − 100n 2 + 3 = Θ (n 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 ∑i

= Φ(n 2)

i=1

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 Θ(n) que:
T(n) = Θ(1) if n = 1
T(n) = T(n­1) + Θ(n) if n > 1
Logo teremos a seguinte solucao de recorrência: T (n) = Θ(n 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.