Complexidade de Algoritmos
Após ver um problema e criar um algoritmo para resolvê-lo, gostariamos de saber três coisas:
1 - O algoritmo de fato resolve o problema?
2 - Quanto tempo o algoritmo demora para resolver o problema?
3 - Quanto de memória o algoritmo utiliza?
Nesta apostila vamos discutir os itens 2 e 3, principalmente o 2.
Como medir o tempo
Uma forma simples é colocar o programa em um computador e medir quanto tempo ele demora para rodar. A pergunta que surge é: Qual computador? Sabemos que diferentes computadores com diferentes sistemas operacionais podem rodar programas em tempos muito diferentes.
Precisamos então escolher uma métrica que mede o tempo de execução de um programa independente do computador e sistema operacional.
Uma ideia é criar uma definição de "operação" de um processador. Uma operação seria uma conta ou atribuição de memória. Podemos considerar uma operação como sendo um ciclo de um processador X.
Vamos considerar uma operação como sendo um ciclo que um processador teórico faz. Qual processador teórico? Mais tarde nesse tutorial veremos que não faz muita diferença qual processador escolhemos.
Para medir o tempo de um programa vamos sempre usar esse processador teórico e ver quantas operações ele faz.
Agora que encontramos uma boa forma de medir o tempo de um programa, queremos saber como ele se comporta para entradas de vários tamanhos.
Exemplo 1:
Vamos criar uma função que recebe um vetor de tamanho N e diz se o primeiro e o últimos elementos são iguais.
void funcao(int v[], int n) {
if (v[0] == v[n-1])
printf("igual");
else
printf("diferente");
}
Sendo k o número de operações executadas dentro dessa função.
Para vetores de tamanho 1 esse algoritmo faz k operações.
Para vetores de tamanho 2 esse algoritmo faz k operações.
Para vetores de tamanho 3 esse algoritmo faz k operações.
É trivial perceber que independente do tamanho do vetor, o algoritmo executa k operações.
Podemos então criar uma função matemática para dizer o número de operações do algoritmo dependendo do tamanho do vetor. Essa função seria naturalmente f(x) = k. Onde x é o tamanho do vetor.
Exemplo 2:
Vamos criar uma função que recebe um vetor de tamanho N e retorna a soma de todos os elementos do vetor.
int funcao(int v[], int n) {
int soma = 0;
for (int i = 0; i < n; i++) {
soma += v[i];
}
return soma;
}
Sendo k o número de operações executadas dentro do loop.
Para vetores de tamanho 1 esse algoritmo faz 1*k operações.
Para vetores de tamanho 2 esse algoritmo faz 2*k operações.
Para vetores de tamanho 3 esse algoritmo faz 3*k operações.
A função matemática que descreve o número de operações que esse algoritmo executa é claramente f(x) = x*k.
Exemplo 3:
Vamos criar uma função que recebe um vetor de tamanho N e um número "num" e retorna 1 se o número "num" está no vetor e 0 caso contrário.
int Existe(int v[], int n, int num) {
for (int i = 0; i < n; i++) {
if (v[i] == num)
return 1;
}
return 0;
}
Seja v = {0, -1, 17, 9, 2} e k o número de operações dentro do loop.
Para num = 0, esse algoritmo faz 1*k operações.
Para num = 20, esse algoritmo faz 5*k operações.
Como escrevemos então uma função matemática, que depende somente do tamanho N do vetor, para dizer o número de operações que a função Existe executa? A resposta é simples: impossível!
O número de operações dessa função depende não somente do N mas também dos valores do vetor "v" e do número "num".
O que podemos afirmar sobre esse algoritmo é que ele faz no máximo N*k operações.
Em vez de escrever uma função matemática f(x) (x = tamanho do vetor) para dizer o número exato de operações do algoritmo. Vamos escrever uma função que diz o número
máximo de operações que o algoritmo pode fazer. Isto é, vamos escrever quantas operações o algoritmo faz para os piores valores possíveis de "v" e "num".
A pergunta que surge é: Para um vetor de tamanho N, quais os piores valores possíveis de "v" e "num"? É fácil verificar que sempre que "num" não está em "v" o algoritmo vai fazer N*k operações. E já vimos antes que esse é o máximo que o algoritmo pode fazer, logo não existe outros valores para "v" e "num" que façam o programa fazer mais de N*k operações.
Uma outra observação válida é: Também podemos dizer que o exemplo 3 nunca vai fazer mais operações do que N*N*N*N*k + N!. Logo a função f(x) = x*x*x*x*k + x! também diz o máximo de operações que o exemplo 3 faz! Sim, o objetivo nosso será então achar uma função f tal que f(x) seja no máximo o número de operações possíveis do algoritmo E f(x) seja o menor valor possível.
Um esboço de notação O
Na notação O estamos interessados no número máximo de operações que um programa faz quando o tamanho da entrada cresce para infinito. Quando temos uma função do tipo f(x) = x*k, x->inf, onde k é uma constante, não importa muito o valor de k em algum momento x vai ser tão alto que o valor de f(x) vai depender quase que inteiramente de x.
Por este motivo dizemos que f(x) = x*k equivale a f(x) = x*1.
Se um algoritmo leva no máximo f(N) = N*k operações para executar. Dizemos que ele é O(N).
Formalmente diz-se que uma função f(x) é O(g(x)) quando existe uma constante C e um ponto x0, tal que:
$\mid f(x)\mid \leq C \mid g(x)\mid \forall x > x0$
Ou seja, existe um ponto em que g(x), multiplicado por uma constante, ultrapassa f(x) e nunca mais volta a ser menor que ela.
Na prática o que fazemos é o seguinte:
$f(x) = 4x^3 + 2x^2$
Queremos que:
$f(x) \leq Cg(x) \forall x > x0$
Então vamos dar uma "roubada" e elevar todos os caras da função f(x) à maior potência dentro dela:
$4x^3 + 2x^3 = 6x^3$
Agora podemos escolher $C = 6 e g(x) = x^3$
E pronto:
$6g(x) >= f(x) \forall x > 0$
Portanto f(x) é O(g(x)).
Um esboço de notação theta
Dizer que um algoritmo é theta(N) significa que o algoritmo executa em no máximo N operações E N é o menor valor possível.
Ou seja, a notação theta é exatamente a que buscamos!
Vamos usar sempre a notação theta então?
Não! Nem sempre é fácil verificar que um algoritmo O(N^2) na verdade também é O(N^1.9). E mesmo que conseguimos provar que ele seja O(N^1.9), não é o bastante. Ele pode ser O(N^1.8) também!
Na Maratona utilizaremos quase sempre a notação O para descrever o tempo dos nossos algoritmos. Mesmo que saibamos o theta do programa também. Afinal resolver um problema num tempo abaixo do limite não traz pontos extras. Enquanto que resolver um problema num tempo acima do limite não serve de nada.
Formalmente, diz-se que uma função f(x) é Theta(g(x)) quando existe C1, C2 e x0 tal que:
$C1 \mid g(x) \mid <= \mid f(x) \mid <= C2 \mid g(x) \mid \forall x > x0$
