Aula de João Guilherme
Aviso: Esta aula é puramente teórica e não é estritamente necessária para continuar o curso, caso o leitor não esteja entendendo bem a matemática usada é recomendado que ele pule esta aula e volte a ela num futuro quando ele tiver mais maturidade matemática.
Vimos já muitas vezes como resolvemos problemas, porém apenas na aula 5 é que fomos nos preocupar com o tempo gasto pelo nosso programa. Em geral os problemas nos dão um limite de 1 segundo para que o programa imprima a resposta, também normalmente isso é equivalente a operações simples em um computador (para sites e questões mais antigas esse valor pode ser menor). Vamos agora pensar então em como quantificar esse tempo gasto pelo programa para gerar uma saída.
A ideia mais simples é usar o número de linhas de um programa, mas isso falha rapidamente, pois se usarmos alguma estrutura de repetição (como um for ou um while), uma das linhas será repetida várias vezes pelo programa, assim temos que os dois programas abaixo demoram tempos consideravelmente distintos.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
cin >> a >> b; | |
c = a + b; | |
cout << c; |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
cin >> n; | |
for(int i = 0; i < n; ++i){ | |
cin >> x[i]; | |
} |
Então podemos refinar um pouco nossa ideia, agora tentemos contar quantas linhas são executadas pelo computador, dessa forma podemos diferenciar muito bem os dois programas anteriores, pois para o computador eles são:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
cin >> a >> b; | |
c = a + b; | |
cout << c; |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
cin >> n; | |
int i = 0; | |
cin >> x[0]; | |
++i; | |
if(i >= n){ | |
break; | |
} | |
cin >> x[1]; | |
++i; | |
if(i >= n){ | |
break; | |
} | |
cin >> x[2]; | |
++i; | |
if(i >= n){ | |
break; | |
} | |
... | |
cin >> x[n - 1]; | |
++i; | |
if(i >= n){ | |
break; | |
} |
Que claramente têm uma quantidade diferente de linhas, o segundo inclusive tem uma quantidade variável.
Porém, essa é a melhor medida que podemos usar? Se estamos atrás de precisão ela é bem ruim. Primeiro pois nem toda linha tem o mesmo custo num computador, adições são mais rápidas que multiplicações e estas são bem mais rápidas que tirar módulo. Além disso, tudo depende da arquitetura do computador, para alguns checar memória é mais rápido que operações aritméticas, outros são otimizados para determinados tipos de multiplicação, uns reduzem o consumo de memória em troca de tempo, etc. Por outro lado todas essas variações são variações de constantes, então se quisermos aproximar de uma forma geral quanto tempo um programa demora rodando, devemos usar um método que ignora mudanças de constantes. Para este fim foram criadas as notações assintótica.
Quando analisamos assintoticamente um programa, nós nos preocupamos apenas com como o custo do programa varia a medida que sua entrada cresce, isso pode parecer meio simplista, por exemplo um programa que custa operações parece muito pior que um que custa para um n pequeno, mas a medida que n cresce, o segundo algoritmos gasta bem mais tempo que o primeiro (para , o primeiro consome em torno de 20000 operações, enquanto o segundo vai consumir 1000000 de operações), assim vemos que é uma forma válida de análise.
Notação O-grande
A notação O-grande é uma das notações assintóticas mais comuns e por analisar o pior caso é o que nós desejamos usar. A definição formal dela é a seguinte:
, se existe e , tais que para todo , .
Em sua definição já é fácil ver que ela ignora constantes, essa notação nos permite falar informalmente que uma função é menor que a outra, além de nos dar uma ótima noção de como o tempo gasto por um programa cresce com o n(e isso vai funcionar para qualquer computador independente de sua arquitetura).
Agora analisemos algumas propriedades dessa notação.
Propriedade 1:
Se , .
Prova da propriedade 1:
Como temos , existe um e um , tais que para todo , . Tomando , conseguimos que para todo , , que nos dá pela definição que .
Propriedade 2:
Se e sendo e são reais, .
Prova da propriedade 2:
Como temos , existe um e um , tais que para todo , .
Tomando agora temos que a prova segue da mesma forma que a da propriedade 1.
Vejamos agora algumas vantagens e desvantagens da notação O-grande:
Propriedade 3:
Se e , então .
Prova da Propriedade 3:
Definamos , , , de forma análoga à anterior, então se tomarmos e , temos que:
, sendo que a desigualdade é válida para n maior ou igual ao maior dentre e , que foi como definimos , assim usando a definição da notação, a propriedade 3 é verdadeira.
Vantagens | Desvantagens |
|
|
Agora analisemos agora algumas complexidades, em ordem de "menor" para "maior".
O(1)
Um algoritmo que sempre vai demorar a mesma quantidade de tempo, independente da entrada, ou seja, de tempo constante.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
cin >> a >> b; | |
c = a + b; | |
cout << c; |
Esse algoritmo custa uma quantidade de operações proporcional ao logaritmo do número, assim se elevamos n ao quadrado, duplicamos o tempo necessário para o algoritmo gerar resposta, o algoritmo mais conhecido nessa complexidade é a busca binária, e o mais simples é tirar a parte inteira do logaritmo de um número.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//busca nos dígitos binários do número | |
//não é uma busca binária | |
//imprime a parte inteira da raiz de n | |
int n, sq = 0, test; | |
cin >> n; | |
for(int pot = 31; pot >= 0; --pot){ | |
test = sq + (1 << test); | |
if(test*test <= n) sq = test; | |
} | |
cout << sq << "\n"; |
Um algoritmo que cresce como a raiz do próprio n, assim se multiplicamos n por quatro, esse programa demora 2 vezes a mais que antes.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// calcula a parte inteira da raiz de n | |
int n, sq; | |
cin >> n; | |
for(sq = 1; sq*sq <= n; ++sq); | |
--sq; | |
cout << sq << "\n"; |
Conhecido como linear. Geralmente um loop que vai de 0 a algum múltiplo fixo de n.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
cin >> n; | |
for(int i = 0; i < n; ++i){ | |
cin >> x[i]; | |
} |
Os algoritmos primeiramente encontrados nessa categoria são as ordenações rápidas por comparação (quicksort, merge-sort, etc).
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//ordenação usando a STL | |
int n, v[100000]; | |
cin >> n; | |
for(int i = 0; i < n; ++i){ | |
cin >> v[i]; //custa O(n) | |
} | |
sort(v, v + n); //ordena o vetor, custa O(nlog(n)) | |
//n + nlog(n) = O(nlog(n)) |
Conhecidos como algotitmos quadráticos, o programa demora tempo proporcional ao quadrado do n. Dessa forma se duplicamos o n, o tempo fica quatro vezes maior. Qualquer código que tenha que ler/preencher uma matriz quadrado de dimensão n custo pelo menos isso.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//ler as entradas de uma matriz | |
int n, G[1000][1000]; | |
for(int i = 0; i < n; ++i){ //Temos O(n*custo do for interno) | |
for(int j = 0; j < n; ++j){ //Termos O(n*operação do for) | |
cin >> G[i][j]; //O(1) | |
} | |
} | |
//Assim a complexidade é O(n*O(n*(O(1)))) = O(n^2) |
Conhecida como classe exponencial, os algoritmos dessa classe geralmente são força bruta. Normalmente esses algoritmos têm que percorrer todos os subconjuntos de um conjunto de n elementos.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//Soma de conjunto, O(n*2^n) | |
int n, v[20], m; | |
cin >> n >> m; | |
for(int i = 0; i < n; ++i){ | |
cin >> v[i]; //leitura, O(n) | |
} | |
for(int mask = 0; mask < (1 << n); ++mask){ //passa por todos os subconjuntos O(2^n) | |
int soma = 0; | |
for(int i = 0; i < n; ++i){ //loop O(n) | |
if((1 << i)&mask){ //checa se um elemento está nesse subconjunto | |
soma += v[i]; | |
} | |
} | |
if(m == soma){ | |
for(int i = 0; i < n; ++i){ | |
if((1 << i)&mask){ | |
cout << i << " "; | |
} | |
} | |
cout << "\n"; | |
break; | |
} | |
} |
Algoritmos que rodam em tempo proporcional ao fatorial, normalmente algoritmos dessa classe são força bruta. Um exemplo é o cacheiro viajante por força bruta.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//Checar a posição lexicogŕafica de uma ordem de um vetor, O(n * n!) | |
int n, v[10], u[10], ans, stop; | |
cin >> n; | |
for(int i = 0; i < n; ++i){ | |
cin >> v[i]; //leitura, O(n) | |
} | |
for(int i = 0; i < n; ++i){ | |
u[i] = v[i]; //copio o vetor para outro, O(n) | |
} | |
sort(u, u + n) //ordenação, O(nlog(n)) | |
for(ans = 0; 1; ++ans){ | |
stop = 0; | |
for(int i = 0; i < n; ++i){ //checa se os vetores são iguais, O(n) | |
if(u[i] != v[i]) break; | |
if(i == n - 1) stop = 1; | |
} | |
if(stop){ | |
break; | |
} | |
next_permutation(u, u + n); //transforma o u na próxima ordenação do vetor na ordem lexicográfica, pode se repetir n! vezes | |
} | |
cout << ans << "\n"; |
Por fim, vejamos algumas simplificações de expressões usando nossa notação, e algumas questões de aplicação.
Exemplo 1:
Exemplo 2: , para qualquer q maior que 0.
Exemplo 3: , para quaisquer constantes a e b com a maior que 1.
Questão 1: Dê a notação O simplificada da seguinte expressão: .
Questão 2: Temos uma questão cuja entrada é um número n, você conseguiu uma solução , qual o maior valor de n para o qual você tem certeza (supondo um juiz moderno e constante pequena) que seu programa vai passar?
Questão 3: Você se deparou com um problema onde você deve fazer uma busca binária em cada um dos subconjuntos de um conjunto de n elementos, qual a complexidade assintótica (notação O) desse algorítimo?
As aulas do Curso Noic de Informática são propriedade do Noic e qualquer reprodução sem autorização prévia é terminantemente proibida. Se você tem interesse em reproduzir algum material do Curso Noic de Informática para poder ministrar aulas, você pode nos contatar por esta seção de contato para que possamos fornecer materiais específicos para reprodução.