# Aula 02

### Referências úteis :

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


***





### Contador Binário

```java
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 : 

```java
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.