Antes de começarmos a estudar os diferentes algoritmos e estruturas de dados que usaremos no mundo da programação competitiva, primeiro precisamos entender como medir a eficiência de um programa, como sabemos que um algoritmo é melhor do que outro?
É de suma importância conseguirmos responder essa pergunta, já que temos um tempo limitado para resolver cada problema (geralmente 1 segundo), e temos que ter uma boa noção de qual algoritmo consegue rodar abaixo desse tempo em diferentes tamanhos de entrada.
Para isso, usamos a complexidade de tempo e complementarmente a complexidade de espaço.
A complexidade de tempo de um algoritmo nos informa como o tempo de execução de um algoritmo cresce em função do tamanho da entrada, se independente da entrada o tempo é sempre o mesmo, chamamos isso de complexidade de tempo constante, e representamos usando O(1), vamos entender mais sobre isso a seguir.
Por exemplo, considere o seguinte algoritmo:
int soma(int n) {
int soma = 0;
for (int i = 0; i < n; i++) {
soma += i;
}
return soma;
}Esse algoritmo recebe um número n e retorna a soma de todos os números de 0 até n - 1.
Por exemplo, se n = 5, o algoritmo retorna 0 + 1 + 2 + 3 + 4 = 10.
A complexidade de tempo desse algoritmo é O(n), pois ele executa n operações, uma para cada número de 0 até n - 1, isso é chamado de crescimento linear.
Chamamos essa notação de Big O, ela representa o pior caso de um algoritmo, ou seja, a quantidade máxima de operações que um algoritmo pode executar.
Vejamos outro exemplo:
int soma(int n) {
int soma = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
soma += i + j;
}
}
return soma;
}Esse algoritmo também recebe um número n porém adicionamos um laço de repetição a mais.
Por exemplo, se n = 3 o algoritmo retorna (0 + 0) + (0 + 1) + (0 + 2) + (1 + 0) + (1 + 1) + (1 + 2) + (2 + 0) + (2 + 1) + (2 + 2) = 18.
Podemos perceber então que a complexidade desse algoritmo é bem maior do que a do algoritmo anterior, isso se dá pois cada número de 0 até n - 1 é somado com cada número de 0 até n - 1, isso nos dá n * n operações.
A complexidade de tempo desse algoritmo é O(n^2), temos um crescimento quadrático.
Aqui estão alguns exemplos das complexidades de tempo mais comuns:
- O(1): Constante
- O(log n): Logarítmica
- O(n): Linear
- O(n log n): Linearítmica
- O(n^2): Quadrática
- O(n^3): Cúbica
- O(2^n): Exponencial
É importante se atentar a complexidade de tempo de um algoritmo, pois ela pode ser a diferença entre um algoritmo que roda em 1 segundo e um que roda em 1 minuto, como podemos ver no gráfico abaixo:
Ao longo da nossa jornada, vamos estudar algoritmos que possuem complexidades de tempo diferentes, levando em conta os diferentes problemas que vamos enfrentar.
Como vimos no gráfico acima, vamos tentar evitar ao máximo algoritmos com complexidades grandes, tais como O(n^2), dito isso, precisamos entender que nem sempre isso é possível, e que em alguns casos, algoritmos com complexidades maiores são necessários.
Vamos pensar em um exercício que nos peça pra achar o menor valor em um vetor, qual a menor complexidade possível para esse problema?
A menor complexidade possível é O(n)! pois precisamos olhar para cada elemento do vetor para saber qual é o menor valor, não tem como fazer isso sem olhar para cada elemento, veremos problemas muito mais complicados que esse mais para frente, e teremos que usar algoritmos com complexidades ainda piores, assim, é importante entender qual complexidade é aceitável levando em conta o tempo disponível e o tamanho da entrada, para isso, consulte a tabela abaixo:
Para cada tamanho de entrada
Geralmente, uma regra para 1s de time limit é multiplicar o tamanho máximo na complexidade. Se for menor que 10⁸ passa tranquilamente, se for na casa do 10⁸, passa apertado dependendo da sua implementação, se for maior, dificilmente passa.
Por exemplo, se o tamanho de O(n^3), então 400³ = 6.4 * 10⁷, o que significa que o algoritmo deve passar o problema.
Normalmente, nas competições de programação, memória não é algo que nos preocupamos muito, já que o limite geralmente é bem alto, entretanto, é importante entender também a complexidade de espaço de um algoritmo, pois ainda sim, ela pode ser um fator limitante.
Por exemplo, considere o seguinte algoritmo:
#include <bits/stdc++.h>
int soma(int n) {
vector<int> numeros(n);
int soma = 0;
for (int i = 0; i < n; i++) {
soma += i;
}
return soma;
}Esse algoritmo recebe um número n e retorna a soma de todos os números de 0 até n - 1, usando uma lista para armazenar os números.
A complexidade de espaço desse algoritmo é O(n), pois ele ocupa n posições na memória, uma para cada número de 0 até n - 1.
Vejamos outro exemplo:
#include <bits/stdc++.h>
int soma(int n) {
vector<vector<int>> numeros(n, vector<int>(n));
int soma = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
soma += i + j;
}
}
return soma;
}Note que esse algoritmo também recebe um número n e também retorna a soma de todos os números de 0 até n - 1, porém usamos uma matriz para armazenar os números, cada linha da matriz é um vetor de 0 até n - 1, estamos consumindo mais memória e tendo o mesmo resultado.
Isso nos dá uma complexidade de espaço de O(n^2), pois ele ocupa n * n posições na memória, cada número de 0 até n - 1 é armazenado n - 1 vezes, podemos visualizar isso rodando os dois exemplos acima e printando a variável numeros, assim como o resultado da soma.
Exemplo 1
soma(10)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
45Exemplo 2
soma(10)
[[0, 1, 2, 3, 4, 5, 6, 7, 8, 9], [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]]
45Perceba que nesse exemplo simples, estamos gastando mais memória sem necessidade, geralmente isso não é um problema, e as vezes até usamos mais memória para alcançar um desempenho melhor, mas é importante entender que isso também é um fator a ser considerado, e que pode nos afetar negativamente caso sejamos descuidados.