$\log{\log n} \ \log n <=> \log n^2 \ 1000 (\log n)^2 \ \frac{n}{\log n} \ 0.005 n^{0.000001} \ 70n \ 50n \log n \ 10n^{\pi} 30 n^3 \log n <=> n^3 \log n + 90 n^2 \log n \ (1.5)^{(\log n)^2} \ n^{\log \log n} \\$

Exercício 2

(a) $f(n) = n^2 + n => O(s(n) = n^2)$ e $g(n) = n^2 => O(r(n) = n^2)$
(b) $f(n) = n^2 => O(s(n) = n^3)$ e $g(n) = n => O(r(n) = n^3)$

Exercício 3

Exercício 4

(a)

Multiplicar(u, v, n) //multiplicar os numeros u e v, ambos de n bits

    Se n == 0, retornar 0 // caso base

    Dividir u em duas metades: a e b
    Dividir v em duas metades: c e d
    ac = Multiplicar(a,c,n/2)
    ad = Multiplicar(a,d,n/2)
    bc = Multiplicar(b,c,n/2)
    bd = Multiplicar(b,d,n/2)

    Retornar ac*2^n + (ad+bc)*2^(n/2) + bd

(b) Recorrência $T(n) = 4T(n/2) + O(n)$ (supondo que a multiplicacao por 2^n toma tempo n), logo complexidade $O(n^2)$

Exercício 5

(a) Como mostrar que $\lim_{n \rightarrow \inf}{ \frac{ (\log n)^{100} }{ n^{\epsilon} } } = 0$ ?
(b) $2^{n+1} = 2 \cdot 2^n = O(2^n)$ , pois existem constantes a, b e $n_0$ tal que $a2^n+b \geq 2 \cdot 2^n$ para $n \geq n_0$
(c) Acho intuitivamente que a afirmação é verdadeira, mas não sei como justificar.

Exercício 6

(a) Se n é par, temos $T(n) = \frac{1}{4}(3n^2 + 14n - 16)$ , se n é ímpar, temos $T(n) = \frac{1}{4}(3n^2 + 14n - 13)$ .
(b) Se n é par, temos $T(n) = 3(2^{\frac{n-2}{2}} + 2^{\frac{n}{2}}) - 3$ , se n é ímpar temos $T(n) = 2^{\frac{n+3}{2}} - 3$ .
(c) $T(n) = 3^{n-1}$ - esse eu suei pra fazer, viu?

Exercício 7

Exercício 8

ContaMaior (no_heap, x, k)
    se (valor(no_heap) < x)
        numMaior++

    se (numMaior > k)
        retornar

    ContaMaior(esq(no_heap),x,k)
    se (numMaior > k)
        retornar
    ContaMaior(dir(no_heap),x,k)

variável global numMaior
numMaior = 0
ContaMaior(raiz_heap,x,k)
se (numMaior > k)
    retornar "NAO"
senão
    retornar "SIM"

Exercício 9

(a)

Ordenar C
Para cada elemento i de C, faça:
    fazer uma busca binária em C pelo elemento de valor x-i
    se existe o elemento x-i, retornar "SIM"
retornar "NAO"

(b)

A = primeiro_elemento(C), B = ultimo_elemento(C)
enquanto (A <= B) faça:
    se (A+B == x) retornar "SIM"
    senão se (A+B > X) B--
    senão A++;
retornar "NAO"

Exercício 10

MenorDist(P, ini, fim) // menor distancia do conjunto de pontos P[ini] ate P[fim]
    se (ini >= fim) retornar INFINITO
    meio = (ini + fim)/2
    menorEsq = menorDist(P,ini,meio), menorDir = menorDist(P,meio+1,fim)
    menorTotal = minimo entre menorEsq e menorDir

    // neste trecho, vamos pegar os resultados dos dois lados (esquerdo e direito),
    // que ja vieram ordenados pelo valor da coordenada Y e vamos juntar em uma nova lista ordenada
    // pelo valor da coordenada Y de cada ponto - procedimento semelhante ao mergesort
    criar um vetor de pontos A de tamanho fim-ini+1
    pEsq = ini, pDir = meio+1, c = 1
    enquanto (pEsq <= meio E pDir < fim) faça:
        ponto A[c] = ponto com menor Y entre P[pEsq] e P[pDir]
        incrementar o ponteiro do lado escolhido e o valor de c
    enquanto (pEsq <= meio) faça:
        A[c] = P[pEsq], pEsq++, c++
    enquanto (pDir < fim) faça:
        A[c] = P[pDir], pDir++, c++
    copiar A para P[ini]...P[fim]

    para cada ponto i em P, faça:
        Checar se a distância do ponto i para os 6 próximos pontos na lista é menor que o valor de "menor"
        Se for, atualizar "menor"
    retornar menor

Exercício 12

(a)

MaiorSeq[1] = 1
para i de 2 até N, faça:
    MaiorSeq[i] = 1
    para j de 1 até i-1, faça:
        se (valor[i] > valor[j])
            MaiorSeq[i] = maximo (MaiorSeq[i], MaiorSeq[j]+1)
retornar o maior valor encontrado em MaiorSeq

(b)

MaiorSeq[1] = Peso[1]
para i de 2 até N, faça:
    MaiorSeq[i] = Peso[i]
    para j de 1 até i-1, faça:
        se (valor[i] > valor[j])
            MaiorSeq[i] = maximo (MaiorSeq[i], MaiorSeq[j]+Peso[i])
retornar o maior valor encontrado em MaiorSeq

Exercício 13

Ordenar as sequencias S1 e S2
P1 = 1, P2 = 1, PS = 1
Enquanto (P1 <= N e P2 <= N) faça:
    Se (S1[P1] == S2[P2]) faça:
        S[PS] = S1[P1]
        PS++, P1++, P2++
    Senão se (S1[P1] < S2[P2])
        S[PS] = S1[P1]
        PS++, P1++
    Senão
        S[PS] = S2[P2]
        PS++, P2++
Retornar S

Pior caso: $O( n \log n )$
O melhor caso depende do algoritmo de ordenação utilizado, podendo ser até $O(n)$

Exercício 14

Minimo(ini, fim, eps)
    vetor de pontos P[4] = { ini, (ini+fim)/3, 2*(ini+fim)/3, fim }
    Se (fim - ini >= 2 * eps) retornar (ini+fim)/2
    Achar o indice x do ponto em P que possui o menor valor [[$ F(P_i) $]]
    Se X == 0, retornar Minimo(P[0],P[1],eps)
    Se X == 3, retornar Minimo(P[2],P[3],eps)
    retornar Minimo(P[X-1],P[X+1],eps)

Recorrência:

T(n) <= T( 2*n/3 ) + O(1)

, logo

T(n) = O(log U)

(b) Sim, pois o algoritmo depende somente do logaritmo de um dos valores da entrada

Exercício 15

(a) $\lceil \log_2{n} \rceil$
(b) Busca binária $O(log h)$ , logo $O(\log \log n)$ .

Exercício 16

Um pé no saco, resolver a equação $\sum_{i=1}^{n}{ \sum_{j=i+1}^{n}{ \sum_{k=1}^{j-i}{1} } }$

Exercício 19

Opa! Esse aqui enganou todo mundo! Na verdade, a equação toda $\sum_{k=0}^{n-1}{k \cdot 2^{n-k}}$ tem que ser calculada em tempo logaritmo em função da entrada N - qualquer algoritmo assintoticamente maior que isso será mais do que linear no tamanho da entrada (um algoritmo linear em função de N seria exponencial em relação ao tamanho da entrada!).
A equação pode ser desenvolvida assim:

(2)

$\sum_{k=0}^{n-1}{k \cdot 2^{n-k}} \ 2^n \cdot \sum_{k=0}^{n-1}{\frac{k}{2^{k}} \\$

Digamos $S(n) = \sum_{k=0}^{n-1}{\frac{k}{2^{k}}$ , temos então:

(3)

$S(n) &=& \sum_{k=0}^{n-1}{\frac{k}{2^{k}} \ S(n) &=& \frac{1}{2^1} + \frac{2}{2^2} + \cdots + \frac{n}{2^n} \ 2 \cdot S(n) &=& 1 + \frac{2}{2^1} + \frac{3}{2^2} + \cdots + \frac{n}{2^{n-1}} \ 2 \cdot S(n) - S(n) &=& 1 + \frac{1}{2^1} + \frac{1}{2^2} + \cdots - \frac{n}{2^n} \ S(n) &=& 1 + \sum_{k=1}^{n-1}{ \frac{1}{2^k} } - \frac{n}{2^n}$

Como $\sum_{k=1}^{n-1}{ \frac{1}{2^k} }$ é uma progressão geométrica de razão $\frac{1}{2}$ , podemos calcular seu valor utilizando uma equação fechada:

(4)

$S(n) &=& 1 - \frac{n}{2^n} + \frac{ (\frac{1}{2})^n - 1 }{ \frac{1}{2} - 1 } \ S(n) &=& 1 - \frac{n}{2^n} + 2 \cdot (1 - \frac{1}{2^n})$

Resta então o problema de calcular o valor de $2^n$ em tempo, no máximo, logaritmico. Isso pode ser feito usando divisão e conquista (top-down), com a seguinte recorrência:

(5)

$T(n) = T(n/2)^2 * 2 \mbox{se n impar} \ T(n) = T(n/2)^2 \mbox{se n par}$

Feito isso, calculamos $2^n$ e então podemos calcular facilmente, em tempo constante, $S(n)$ e o resultado final.

page_revision: 17, last_edited: 1176213427|%e %b %Y, %H:%M %Z (%O ago)

Edit Tags History Files Print Site tools + Options

NazaWiki

Kung Fu and the art of computer programming

Primeira lista de exercícios (paa071-l1.pdf)

Exercício 1