Aula Especial: Complexidade

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 $10^8$ 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.

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:

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 $1000 \cdot \log(n)$ operações parece muito pior que um que custa $n$ para um n pequeno, mas a medida que n cresce, o segundo algoritmos gasta bem mais tempo que o primeiro (para $n = 10^6$, 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:

$f(n) = O(g(n))$, se existe $N$ e $c$, tais que para todo $n \geq N$, $f(n) \leq c \cdot g(n)$.

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 $f(n) = O(g(n))$, $f + g = O(g(n))$.

Prova da propriedade 1:

Como temos  $f(n) = O(g(n))$, existe um $c$ e um $N$, tais que  para todo $n \geq N$, $f(n) \leq c \cdot g(n)$. Tomando $c_1 = c + 1$, conseguimos que para todo $n \geq N$, $c_1 \cdot g(n) = c \cdot g(n) + g(n) \geq f(n) + g(n)$, que nos dá pela definição que $f + g = O(g(n))$.

Propriedade 2:
Se $f(n) = O(g(n))$ e sendo $a$ e $b$ são reais, $a \cdot f + b \cdot g = O(g(n))$.

Prova da propriedade 2:

Como temos  $f(n) = O(g(n))$, existe um $c$ e um $N$, tais que  para todo $n \geq N$, $f(n) \leq c \cdot g(n)$.
Tomando agora $c_1 = a \cdot c + b$ 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 $f_1(n) = O(g_1(n))$ e $f_2(n) = O(g_2(n))$, então $f_1 \cdot f_2 = O(g_1 \cdot g_2)$.

Prova da Propriedade 3:

Definamos $c_1$, $c_2$, $n_1$, $n_2$ de forma análoga à anterior, então se tomarmos $c = c_1 \cdot c_2$ e $n = \max(n_1, n_2)$, temos que:

$c \cdot g_1g_2 = (c_1g_1) \cdot (c_2g_2) \geq f_1 \cdot f_2$

, sendo que a desigualdade é válida para n maior ou igual ao maior dentre $n_1$ e $n_2$, que foi como definimos $n$, assim usando a definição da notação, a propriedade 3 é verdadeira.

Vantagens

Desvantagens

Analisamos apenas o que geralmente importa,ou seja qual algoritmo é melhor para valores elevados (de nada adianta ter um algoritmo rápido para n pequenos, porém para o n da questão ele é muito lento). "Limpa" a notação. Em vez de escrevermos $5 \cdot n^3 + 12 \cdot n^{1/2}$, podemos simplesmente escrever $O(n^3)$. Também em vez de usarmos $n + log_2(n) + sen(n) + cos(n)$, podemos escrever simplesmente $O(n)$. Nos permite tentar estimar da complexidade da solução do problema, o que nos permite ter uma noção dos algoritmos que usaremos para resolver a questão. Manipulação de expressões ficam extremamente mais simples (todos os logaritmos são equivalentes). Nosso problema com a arquitetura do computador é resolvido, pois nós ignoramos constantes.

Às vezes uma função é assintoticamente mais rápida que outra, porém para os valores do problema é melhor usar a mais lenta. Por exemplo assintoticamente $(\log n)^4$ é "menor" que $\sqrt n$, mas para n menor que $2\cdot 10^{12}$ $\sqrt n$ é menor que $(\log n)^4$, e portanto para uma questão com n menor que esse valor, seria melhor usar o segundo algoritmo. Em alguns casos os fatores menores e as constantes podem realmente lhe fazer receber um TLE (time limit exceeded), em especial em questões com tempos limites muito estritos (o SPOJ internacional é particularmente famosos por esse tipo de problema). Por vezes a solução real do problema é lenta e não devia passar no tempo, porém devida a alguma estrutura na entrada não especificada na entrada da questão permite que o problema passe (Caminhão e Cavalos no URI), ou talvez a solução certa tenha uma complexidade alta e você deve usar heurísticas para tornar o programa mais rápido.

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.

 

$O(\log(n))$

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.

 

$O(\sqrt 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.

 

$O(n)$

Conhecido como linear. Geralmente um loop que vai de 0 a algum múltiplo fixo de n.

 

$O(n \cdot \log(n))$

Os algoritmos primeiramente encontrados nessa categoria são as ordenações rápidas por comparação (quicksort, merge-sort, etc).

 

$O(n^2)$

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.

 

$O(2^n)$

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.

 

$O(n!)$

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.

 

Por fim, vejamos algumas simplificações de expressões usando nossa notação, e algumas questões de aplicação.

Exemplo 1: $O(\sqrt n + n^2 + n^3 + n \log(n)) = O(n^3)$

Exemplo 2: $O(n^q+ \log(n)) = O(n^q)$, para qualquer q maior que 0.

Exemplo 3: $O(a^n + n^b) = O(a^n)$, para quaisquer constantes a e b com a maior que 1.

Questão 1: Dê a notação O simplificada da seguinte expressão: $\cos(n) + 1000 \cdot n + n^2$.

Questão 2: Temos uma questão cuja entrada é um número n, você conseguiu uma solução $O(\sqrt n)$, 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.