lista4.md 5.8 KB
1. Escreva uma função que recebe um vetor com n letras A’s e B’s e, por meio de trocas, move todos os A’s para o início do vetor. Sua função deve consumir tempo $O(n)$.
A função vai receber o vetor C que possi n elementos.
OrdenaAB(C, n)
1. dir <- 1
2. esq <- n
3. enquanto dir < esq
4. se C[dir] igual 'A'
5. dir <- dir + 1
6 senão se C[esq] igual 'B'
7. esq <- esq + 1
8. senão
9. C[esq] <-> C[dir]
10. dir <- dir + 1
11. esq <- esq + 1
Note que em cada interação obrigatoriamente dir vai ser subtraído ou esq vai ser adicionado. Com isso o número máximo de vezes que a linha 3 pode ser executada é $O(n)$. Note que as linhas posteriores a essa vão ser executadas menos vezes que essa, portanto o código continuará $O(n)$.
2. Escreva uma função que rearranje um vetor v[p..r] de inteiros de modo que tenhamos v[p..j−1] ≤ 0 e v[j..r] > 0 para algum j em p..r+1. Faz sentido exigir que j esteja em p..r? Procure fazer uma função rápida que não use vetor auxiliar. Repita o exercício depois de trocar v[j..r] > 0 por v[j..r] ≥ 0. Faz sentido exigir que v[j] seja 0?
OrdenaZero(v, n)
1. dir <- 1
2. esq <- n
3. enquanto dir < esq
4. se C[dir] <= 0
5. dir <- dir + 1
6 senão se C[esq] > 0
7. esq <- esq + 1
8. senão
9. C[esq] <-> C[dir]
10. dir <- dir + 1
11. esq <- esq + 1
Não faz muito sentido exigir que j esteja em p..r, pois pense no caso em que temo o vetor completo de números negativas, nesse caso se j estiver em p..r, algum desses elemntos será > 0, criando uma contradição.
Para trocarmos v[j..r] > 0 por v[j..r] ≥ 0 basta alterar a linha 6 do programa. No entanto não faz sentido exigir que v[j] seja 0, pois dessa forma nunca saberíamos em qual parte do vetor encontramos os zeros.
3. Sejam X[1..n] e Y [1..n] dois vetores, cada um contendo n números ordenados. Escreva um algoritmo $O(lg n)$ para encontrar uma das medianas de todos os 2n elementos nos vetores X e Y .
Vamos tentar usar o método de divisão e consquista. Vamos supor que temos os seguintes vetores:
1 2 3 4 5 6 7 1 2 3 5 8 9 9
É claro que a mediana deles é 4 e 5. Vamos pegar a mediana do vetores:
1 2 3 (4) 5 6 7 1 2 3 (5) 8 9 9
O vetor em qual a mediana for menor deve ser aquele em que vamos pegar a parte da direita, o que a mediana for maior pegamos a da esquerda.
4 5 6 7 -> 4 (5) 6 7 -> 4 5 -> (4) 5 -> 4
1 2 3 5 -> 1 2 (3) 5 -> 3 5 -> 3 (5) -> 5
Na nossa função vamos ter dois vetores v1 e v2 com n elementos. Suponha que 3/2 = 1
Mediana(v1, v2, p1, q1, p2, q2)
1. se q1-p1 = 1
2. tmp <- [v1[p1], v1[q1], v2[p2], v2[q2]]
3. tmp <- ordena tmp
2. retorna tmp[3]
3.
4. j1l <- p1+(q1-p1)/2
5. j2l <- p2+(q2-p2)/2
6. j1u <- p1+(q1-p1+1)/2
7. j2u <- p2+(q2-p2+1)/2
8.
9. tmpv1 <- v1[j1l] + v1[j1u]
10. tmpv2 <- v2[j2l] + v2[j2u]
11.
12. se tmpv1 > tmpv2
13. retorna Mediana(v1, v2, p1, j1u, j2l, q2)
15. senão
16. retorna Mediana(v1, v2, j1l, q1, p2, j2u)
def Mediana(v1, v2, p1, q1, p2, q2)
if q1-p1 == 1
return (v1[p1,2] + v2[p2,2]).sort[1 , 2].join(" ")
end
j1l = p1+(q1-p1)/2
j2l = p2+(q2-p2)/2
j1u = p1+(q1-p1+1)/2
j2u = p2+(q2-p2+1)/2
tmpv1 = v1[j1l] + v1[j1u]
tmpv2 = v2[j2l] + v2[j2u]
if tmpv1 > tmpv2
return Mediana(v1, v2, p1, j1u, j2l, q2)
else
return Mediana(v1, v2, j1l, q1, p2, j2u)
end
end
size = 30
v1 = Array.new(size) { rand(10...50) }.sort!
v2 = Array.new(size) { rand(10...50) }.sort!
puts v1.join(" ")
puts v2.join(" ")
puts Mediana(v1, v2, 0, size-1, 0, size-1)
sorted = (v1+v2).sort
puts [sorted[(2*size - 1) / 2], sorted[(2*size) / 2]].join(" ")
Vamos provar que é $O(lg{} n)$.
$$T(1) = 1$$ $$T(n) = T(\lceil x/2 \rceil) + O(1)$$ $$T(n) = T(\lceil x/2^i \rceil) + i$$
Vamos supor que $x$ é potencia de 2, ou seja, $x = 2^i$
$$T(x) = T(2^i/2^i) + i$$ $$T(x) = T(1) + i$$ $$T(x) = 1 + lg \space x$$
Vamos provar por indução:
BASE: $x = 1, T(1) = 1$ e $1 + lg \space 1 = 1$
HIPÓTESE: $T(x/2) = 1 + lg \space x/2 = lg \space x$
$$T(x) = T(x/2) + 1 = (pela HI) = lg \space x + 1 $$
Que é o que queríamos provar.
4. Para esta questão, vamos dizer que a mediana de um vetor A[p..r] com número inteiros é o valor que ficaria na posição A[b(p + r)/2c] depois que o vetor A[p..r] fosse ordenado. Dado um algoritmo linear “caixa-preta” que devolve a mediana de um vetor, descreva um algoritmo simples, linear, que, dado um vetor A[p..r] de inteiros distintos e um inteiro k, devolve o k-ésimo mínimo do vetor. (O k-ésimo mínimo de um vetor de inteiros distintos é o elemento que estaria na k-ésima posição do vetor se ele fosse ordenado).
Kesimo(A, p, r, k)
m <- mediana(A, p, r)
part <- particiona_com_elemento(A, p, r, m)
se p > k
retorna Kesimo(A, p, part, k)
senao se p < k
retorna Kesimo(A, part, r, k)
retorna A[part]
Note, o particiona é $O(n)$, assim como a mediana. Portanto o tempo de consumo desse algorítmo será $T(n) = T(n/2) + O(n) = T(n/2) + an $. Vamos provar que é $O(n)$. Note que $T(1) = 1$
BASE: $T(1) = 1 \leq c * 1 $
HIPÓTESE: $T(n/2) \leq cn/2 x$
$$ T(n) = T(n/2) + O(n) \leq c * n/2 + a * n \leq (c/2+a) n = c * n - n * c/2 + a * n$$
Só falta peovar que:
$$ - nc/2 + a * n \leq 0 $$ $$ a * n \leq n * c/2 $$ $$ 2 * a \leq c $$
Como $a$ é uma contante que depende do particiona e da mediana e existe, logo existe $c$.