complexity.md

theme	transition	title	enableMenu	enableSearch	enableChalkboard	slideNumber	controls
white	fade	Complexidade de algoritmos	true	true	true	true	true

Complexidade de algoritmos

---

---

Definição

A complexidade é usada para medir a velocidade de um algoritmo

---

Por que isso é importante?

1. Limites de tempo estipulados.
2. Estratégias de resolução de problemas

---

Qual será a nossa ferramenta?

Notação assintótica

---

Exemplos de funções

• N²
• (3/2) *  N²
• 9999  * N²
• N²/1000
• N²+ 100 * N
• etc.

---

Gráfico

---

Mesma classe

O(N²)

---

Agora, no código

---

int main() {
    vector<int> vetor = {4, 7, 2, 9, 1, 5, 8, 3, 6};
    int valorBusca = 5;
    int N = vetor.size();
    
    int indice = -1;
    for (int i = 0; i < N; ++i) {
        if (vetor[i] == valorBusca) {
            indice = i;
        }
    }
    
    return 0;
}

---

Qual a complexidade de código que vimos?

---

O código é O(N), mas por que?

Tamanho da entrada VS Quantidade de vezes que o código repete

---

Outro exemplo

int main() {
    vector<int> vetor = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    
    int soma = 0;
    for (int i = 0; i < vetor.size(); ++i) {
        soma += vetor[i];
    }
    
    cout << "A soma dos elementos do vetor é: " << soma << endl;
    
    return 0;
}

---

Resposta: O(N)

---

int main() {
    int N = 5; // Tamanho da matriz (5x5)

    vector<vector<int>> matriz(N, vector<int>(N));
    int valor = 1;

    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            matriz[i][j] = valor;
            valor++;
        }
    }
}

---

Resposta: O(N^2)

---

int buscaBinaria(vector<int>& vetor, int chave) {
    int esquerda = 0;
    int direita = vetor.size() - 1;

    while (esquerda <= direita) {
        int meio = esquerda + (direita - esquerda) / 2;
        
        if (vetor[meio] == chave)
            return meio; // Chave encontrada, retorna o índice
        else if (vetor[meio] < chave)
            esquerda = meio + 1; // Descarta a metade esquerda
        else
            direita = meio - 1; // Descarta a metade direita
    }

    return -1; // Chave não encontrada
}

---

Resposta: O(log(N))

Vamos entender melhor

---

N vs Iterações

• N = 1 | 1 iteração
• ...
• N = 3 | 2 iterações
• ...
• N = 6 | 3 iterações
• ...
• N = 9 | 4 iterações
• ...
• N = 17 | 5 iterações
• ...

---

N vs Iterações

• N = 33 | 6 iterações
• ...
• N = 65 | 7 iterações
• ...
• N = 129 | 8 iterações

---

2^N | Iteração

2^1 = 2 | 1 iteração

2^2 = 4 | 2 iterações

2^3 = 8 | 3 iterações

2^4 = 16 | 4 iterações

2^5 = 32 | 5 iterações

2^6 = 64 | 6 iterações

2^7 = 128 | 7 iterações

---

Ou seja

Na busca binária, para que eu faça 1 iteração a mais, a entrada precisa dobrar de tamanho

---

Dúvidas até aqui?

---

Lets go

---

int main() {
    int valor;

    cout << "Digite um valor inteiro: ";
    cin >> valor;

    int resultado = valor / 2;

    cout << "A metade do valor inserido é: " << resultado << endl;

    return 0;
}

---

Resposta: O(1)

Quando o código repete um número fixo de vezes, independente da entrada

---

int main() {
    vector<int> vetor = {9, 2, 5, 1, 7, 3, 8, 6, 4};

    sort(vetor.begin(), vetor.end());

    cout << "Vetor ordenado: ";
    for (int num : vetor) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

---

Resposta: O(N * log(N))

---

E como que eu iria fazer para saber isso?

---

E como os limites ajudam a resolver questões?

---

Limite do Judge

1s = 10^7, se quiser forçar um pouco, 10^8

---

Questão beecrowd | 1259

---

Uma solução O(N^2) passa?

---

Então, vamos nos atentar aos limites

---

---

Dúvidas?

---