Aula 02¶

Referências úteis :¶

https://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/amortized.html

Contador Binário¶

public static increment(int[] a) {
    int k = a.length;
    int i = 0;
    while (i < k && a[1] == 1) {
        a[i] = 0;
        i = i +1;
    }
    if (i < k) {
        a[i] = 1;
    }
}

Consumo de tempo (de cada linha do código)¶

Linha	Consumo de tempo
1	O(1)
2	O(k)
3	O(k)
4	O(k)
5	O(1)
6	O(1)

Consumo de tempo : O(k)

Sequência de n chamadas¶

incr(), incr(), incr()…. inc() : n chamadas

Consumo de tempo é $O(nk)$, o que é um exagero (eu não analisei os casos, só supus que toda execução vai ser $O(n)$).

a[0] muda n vezes

a[1] muda $ \frac{n}{2}$ vezes

a[2] muda $\frac{n}{4}$ vezes

.

a[i] muda $\frac{n}{2^i}$ vezes

O custo então pode ser calculado por :

$$ Custo = \sum_{i=0}^{k}{\frac{n}{2^i}} = n \cdot\sum_{i=0}^{k}{\frac{1}{2^i}} < n\cdot\sum_{i=0}^{\infty}{\frac{1}{2^i}} = 2n $$

Assim, podemos provar que o algoritmo é $O(n)$

Custo amortizado¶

O custo amortizado de uma operação é o custo médio da operação quando considerada uma sequência de operações.

Assim, podemos reescrever a eficiência do algoritmo usando a definição acima : **o consumo de tempo de uma sequÊncia de n incrementos é $O(n)$. O custo amortizado de increment() é $O(1)$. **

Tabela Dinâmica (pode ser implementada com fila ou pilha)¶

Implementação :

public class Stack<Item> implements Iterable<Item< {
    private Item[] a;
    private int n;
   	
    public Stack() { //1
        a = (Item[]) new Object[MAX];//2
    }
    
    public boolean isEmpty() {
        return n == 0;
    }
    
    public intSize() {
        return n;
    }
    
    public void push(Item item) {
        if (n == a.length)
            resize(2*a.length);
        a[n++] = item;
    }
    
    public Item pop() {
        Item item = a[n-1];
        a[n-1] = null; //3
        n--;
        if (n > 0 && n < a.length/2){
            resize(a.length/2);
        }
        return item;
    }
    
    private void resize(int cap) {
        Item[]temp = (Item[]) new Object[cap];
        for (int i = 0; i < n; n++) {
            temp[i] = a[i];
        }
    }
}

/*               	 GLOSSARIO JAVA

1 : construtor da pilha
2 : O argumento vai ser o tamanho da pilha
3: O java tem um garbage collector, ou seja, não precisa ficar dando free nas coisas. Mas para o java liberar memória ele tem que ter certeza que não tem um ponteiro para aquele endereço de memória, por isso tornamos aquele ponteiro nulo.

*/

Consumo de tempo¶

Consumo de tempo de push é O(n).
Sequência de push() :
- S0 -> S1 -> S2 -> … Sn
- Si = estado da pilha após o i-esimo push
- custo do push $O(m)$ - operação individual
- custo da sequência = $O(m^2)$ - Exagero!

Análise do push¶

push()	a.length	custo
1	1	1
2	2	1+1 (dobrei para 2)
3	4	1+2(dobrei para 4)
4	4	1
5	8	1+4 (dobrei para 8)
6	8	1
7	8	1
8	8	1
9	16	1+8 (dobrei para 16)

Custo :¶

$$ \sum custos = m + \sum_{i = 0}^{k}2^i = m + 2^k - 1 $$

Mas $k \approx lg(m)$ então : $$ \sum custos < m+2m = 3m $$

Assim, o consumo de tempo de uma sequência de m push() é $O(m)$
O consumo de tempo amortizado de push é $O(k)$ : as operações na quais eu dobro o tamanho da pilha são muito custosas, mas a maioria das operações é constante.