Big O e análise de algoritmos

O panorama: o que medimos?

Quando você pergunta 'quão rápido é este programa?', a resposta em segundos não ajuda muito. Um computador rápido e um lento dão segundos diferentes para o mesmo programa. Então contamos algo que não muda: o número de passos básicos (uma comparação, uma soma, a leitura de uma célula de memória) em função do tamanho da entrada, que chamamos de n.

Dois tipos de custo

Palavras que você vai encontrar

• Tamanho da entrada (n): quantos dados o algoritmo recebe, por exemplo o número de itens de uma lista.
• [[Assintótico|o que acontece quando n fica muito, muito grande]]: olhamos o quadro geral para entradas enormes e ignoramos pequenos detalhes.
• Ordem de crescimento: o 'formato' do crescimento, como 'linha reta' ou 'curva que dispara'.
• Pior, melhor e caso médio: o custo para a entrada mais azarada, a mais sortuda e uma entrada típica.
• Limite inferior: um limite que diz 'nenhum algoritmo consegue fazer melhor do que isto'.

Crescimento de funções e sua ordenação

Algoritmos diferentes crescem de maneiras diferentes. Alguns mal percebem uma entrada maior. Outros explodem. Para compará-los usamos uma pequena família de 'velocidades', da mais suave à mais selvagem.

A ordem é: 1 < log n < √n < n < n log n < n² < n³ < 2ⁿ < n! < nⁿ. Um 'logaritmo' cresce muito devagar: log₂ 1.024 é só 10, e log₂ 1.000.000 é apenas cerca de 20.

O que acontece quando a entrada dobra?

Dois fatos úteis para comparar. Primeiro, o crescimento polinomial (uma potência de n, como n² ou n^1,5) sempre perde para o exponencial (2ⁿ) quando n é grande. Segundo, uma potência de log n, até (log n)¹⁰, sempre perde para uma pequena potência de n como √n quando n é grande. Assim, n log n é menor que n^1,5, porque log n cresce mais devagar que √n. E n / log n é menor que n, mas maior que √n.

Um computador mais rápido ajuda menos do que você pensa. Se um algoritmo faz n² operações e hoje resolve n = 1.000 em um segundo, uma máquina 100 vezes mais rápida resolve só n = 10.000 nesse segundo (porque 10.000² = 100 × 1.000²). Esse mesmo ganho em um algoritmo 2ⁿ soma apenas cerca de 7 ao n.

Notação assintótica: O, Ω, Θ, o, ω

Suponha que um algoritmo faça exatamente 3n² + 10n + 5 passos. Para um n enorme, o 10n e o 5 são minúsculos perto de 3n², e o 3 depende só do computador. Então dizemos que o algoritmo é 'da ordem de n²'. As notações abaixo dão uma maneira precisa de dizer isso.

A definição formal (para funções não negativas)

f(n) = O(g(n)) significa: existem constantes c > 0 e n0 tais que f(n) ≤ c · g(n) para todo n ≥ n0. Em palavras: a partir de certo ponto, f nunca passa de um múltiplo constante de g. Ω é o mesmo com ≥. Θ exige os dois: f = Θ(g) exatamente quando f = O(g) e f = Ω(g).

Exemplo: para mostrar que 100n + 50 = O(n), tome c = 150 e n0 = 1. Para n ≥ 1 temos 100n + 50 ≤ 100n + 50n = 150n. Outro par válido é c = 101 e n0 = 50. Qualquer par que funcione prova a afirmação.

Com limites fica ainda mais fácil. Olhe a razão f(n)/g(n) quando n tende ao infinito. Se tende a 0, então f = o(g). Se tende ao infinito, então f = ω(g). Se tende a uma constante positiva (por exemplo 7), então f = Θ(g).

razão f(n)/g(n) quando n -> infinito

  0               ->  f = o(g)     (f é menor)
  constante > 0   ->  f = Θ(g)     (mesma taxa)
  infinito        ->  f = ω(g)     (f é maior)

Fatos úteis

• n = O(n²) é verdadeiro. O é apenas um limite superior, não precisa ser justo. É como dizer 'tenho menos de 100 anos'.
• Ω sozinho não diz nada sobre limite superior. 'Isto leva pelo menos n passos' pode ser n ou 1.000.000 n.
• 2^(n+1) = Θ(2ⁿ), porque 2^(n+1) = 2 · 2ⁿ é só uma constante maior. Mas 2^(2n) = 4ⁿ = ω(2ⁿ), porque a razão 2ⁿ tende ao infinito.
• A base do logaritmo não importa dentro de O. log₂ n e log₁₀ n diferem por um fator constante, então escrevemos só O(log n).
• Θ é simétrico: se f = Θ(g), então g = Θ(f). O não é: n = O(n²), mas n² não é O(n).
• log₂(n!) = Θ(n log n). Essa soma de logaritmos é a ordem de crescimento justa do logaritmo de um fatorial.
• Alguns pares de funções não são comparáveis. Se f(n) = n e g(n) vale 1 para n par mas n² para n ímpar, então f não é O(g) nem Ω(g).

Contagem de operações em laços

Para achar o Big O de um programa, contamos quantas vezes sua linha principal executa em função de n. Algumas regras resolvem quase todos os casos.

• Um depois do outro: soma. Dois laços em sequência, cada um com n passos, custam n + n = 2n, que é Θ(n).
• Um dentro do outro: multiplica. Um laço de n passos contendo outro laço de n passos custa n × n = n².
• Descarte constantes e termos menores. n² + n é Θ(n²).
• Um if / else: pegue o pior ramo quando você não sabe qual será usado.

Laços simples e laços aninhados

// PT: Um laço que roda n vezes faz n passos: Θ(n).
for (let i = 0; i < n; i++) work();

// PT: Cada par (i, j) com i < j é visitado uma vez: n(n-1)/2 vezes, logo Θ(n²).
// Para n = 10 são 10 * 9 / 2 = 45 vezes.
for (let i = 0; i < n; i++)
	for (let j = i + 1; j < n; j++) work();

Contar pares é como contar apertos de mão numa sala com n pessoas: cada par se cumprimenta uma vez, então há n(n-1)/2 apertos. Contar trios i < j < k funciona igual: n(n-1)(n-2)/6 trios. Para n = 6 são 20. Isso é Θ(n³).

Laços que dobram ou andam em passos variáveis

// PT: i dobra: 1, 2, 4, 8... só cerca de log2(n) iterações: Θ(log n).
for (let i = 1; i < n; i *= 2) work();

// PT: O externo dobra i, o interno roda i vezes: 1 + 2 + 4 + ... + n é cerca de 2n: Θ(n).
for (let i = 1; i < n; i *= 2)
	for (let j = 0; j < i; j++) work();

// PT: O interno pula de i em i: n/1 + n/2 + n/3 + ... é cerca de n log n: Θ(n log n).
for (let i = 1; i <= n; i++)
	for (let j = 0; j < n; j += i) work();

O exemplo do meio é uma soma geométrica: cada termo é o dobro do anterior, então a soma toda é cerca do dobro do último termo. O último exemplo é uma soma harmônica: n/1 + n/2 + ... + n/n, que é n vezes cerca de ln n.

O custo depende do valor, não só do tamanho

Um teste de primalidade simples tenta os divisores d = 2, 3, 4... enquanto d × d ≤ n. No pior caso faz cerca de √n divisões, onde n é o valor testado. Parece suave, mas um número com 100 dígitos tem valor em torno de 10¹⁰⁰, então √n é 10⁵⁰: muito além do possível. Medido pelo número de dígitos, o custo é exponencial.

Melhor caso, pior caso e caso médio

O mesmo algoritmo pode se comportar de modo muito diferente conforme os dados que recebe. Procurando um nome numa lista de n nomes: se for o primeiro, você teve sorte; se for o último (ou não existir), teve azar.

O pior caso é o mais usado, porque é uma promessa: 'nunca será mais lento que isto'. O caso médio precisa de uma hipótese extra que o pior caso não precisa: uma distribuição de probabilidade das entradas (por exemplo, 'todas as posições são igualmente prováveis'). Sem essa hipótese, 'média' não significa nada.

Ordenação por inserção

A ordenação por inserção coloca cada carta nova no lugar certo entre as cartas que você já segura. Numa lista já ordenada, cada carta precisa de uma só comparação: melhor caso Θ(n). Numa lista invertida, cada carta passa por todas as anteriores: pior caso Θ(n²).

Quicksort e seu pivô

O quicksort escolhe um pivô, põe os itens menores de um lado e os maiores do outro, e repete em cada lado. Se o pivô é sempre o primeiro elemento, uma lista já ordenada (ou invertida) é o pior caso: o pivô é o menor item, um lado fica vazio e o outro tem n - 1 itens. O trabalho é n + (n-1) + (n-2) + ... = Θ(n²).

Com um pivô aleatório, nenhuma entrada específica é ruim. O azar agora vem da escolha aleatória, não dos dados. O tempo esperado é Θ(n log n) para toda entrada. Pivôs ruins ainda podem acontecer, mas são raros.

lista ordenada, pivô = primeiro elemento:

[1 2 3 4 5]   pivô 1 -> esq: []     dir: [2 3 4 5]
[2 3 4 5]     pivô 2 -> esq: []     dir: [3 4 5]
[3 4 5]       pivô 3 -> esq: []     dir: [4 5]
...
n níveis, cada um com cerca de n de trabalho -> Θ(n²)

Recorrências e o teorema mestre

Alguns algoritmos resolvem um problema resolvendo cópias menores do mesmo problema. Isso se chama recursão. Para medi-los escrevemos uma equação que diz: 'o custo de tamanho n é o custo das partes menores mais o trabalho extra'. Essa equação é uma recorrência.

Escrevendo as recorrências que você precisa

Para T(n) = T(n-1) + n com T(1) = 1, os valores são T(2) = 3, T(3) = 6, T(4) = 10, T(5) = 15. É a soma 1 + 2 + ... + n = n(n+1)/2. Em Hanói, para mover n discos você move n-1 discos, move o maior disco e move os n-1 discos de novo, então o trabalho dobra a cada disco extra: T(n) = 2ⁿ - 1.

O teorema mestre

Muitas recorrências de divisão e conquista têm a forma T(n) = a · T(n/b) + f(n). Aqui a é o número de chamadas recursivas, n/b é o tamanho de cada chamada e f(n) é o trabalho extra fora das chamadas (dividir e juntar). Compare f(n) com o número n^(log_b a), que é quanto trabalho as 'folhas' da recursão fazem.

'Polinomialmente' quer dizer por um fator de pelo menos n^ε para algum ε > 0. Exemplos: T(n) = 2T(n/2) + n: aqui n^(log₂ 2) = n e f = n, empate, então Θ(n log n). T(n) = 4T(n/2) + n: n^(log₂ 4) = n² vence n, então Θ(n²). T(n) = T(n/2) + n: n^(log₂ 1) = 1, f = n é maior, então Θ(n). Strassen: T(n) = 7T(n/2) + n²: n^(log₂ 7) é cerca de n^2,81, que vence n², então Θ(n^(log₂ 7)).

T(n) = 2T(n/2) + n

profundidade 0:   [ n ]                    -> n
profundidade 1: [n/2]   [n/2]              -> n
profundidade 2: [n/4][n/4][n/4][n/4]       -> n
...
profundidade i: 2^i nós de tamanho n/2^i   -> n

níveis: log2(n)   total = n * log2(n)

A árvore de recursão mostra o porquê. Na profundidade i há 2^i nós, cada um custando n / 2^i, então cada nível soma n. Com cerca de log n níveis, o total é n log n.

Quando o teorema mestre não se aplica

• T(n) = T(n-1) + n e T(n) = 2T(n-1) + 1: o subproblema é n - 1, não n dividido por algo. Use a árvore de recursão, ou expanda e some.
• T(n) = 2T(n/2) + n log n: f(n) é maior que n, mas não polinomialmente maior, então cai entre os três casos básicos. Uma versão estendida dá Θ(n log² n).
• T(n) = T(n/3) + T(2n/3) + n: as duas chamadas têm tamanhos diferentes. A árvore de recursão tem cerca de log n níveis, cada um custando no máximo n, e a resposta é Θ(n log n).

Provando por substituição

Outro método é chutar a resposta e provar por indução. Cuidado: você precisa provar exatamente a afirmação que chutou. Se você supõe T(n/2) ≤ c · n/2 para T(n) = 2T(n/2) + n, obtém T(n) ≤ cn + n. Isso não é ≤ cn, então a prova de T(n) = O(n) falha (e de fato T(n) é Θ(n log n)). Concluir 'cn + n é O(n)' é um erro clássico, porque a constante c precisa continuar a mesma.

Invariantes de laço e prova de corretude

Ser rápido não adianta se a resposta está errada. Um invariante de laço é uma frase sobre as variáveis que é verdadeira toda vez que o laço começa uma nova volta. É um jeito de provar que um algoritmo faz a coisa certa.

Os três passos

// PT: Invariante: quando o teste i < n roda, s é a soma de a[0..i-1].
// Início: i = 0, s = 0 (soma vazia). Manutenção: somar a[i] dá a soma de a[0..i].
// Fim: i = n, então s é a soma do vetor inteiro.
let s = 0;
for (let i = 0; i < a.length; i++) s += a[i];

A ordenação por inserção tem um invariante famoso: no início da volta que insere a[j], a parte a[0..j-1] contém os mesmos elementos do começo, em ordem. Quando j chega a n, o vetor inteiro está ordenado.

Um bom invariante é forte o bastante

Para um laço que calcula o máximo com m = a[0], a frase 'm é igual a algum elemento do vetor' é sempre verdadeira, mas é inútil: no fim ela não diz que m é o maior. O invariante certo é 'm é o maior de a[0..i-1]'. No término, i = n e então m é o maior do vetor inteiro.

Correto não é o mesmo que terminar

Um invariante prova que se o laço termina, a resposta está certa. Você também precisa provar que o laço termina. Na busca binária, se lo = mid + 1 for trocado por lo = mid, o invariante 'se x está no vetor, está em a[lo..hi]' continua verdadeiro, mas quando hi = lo + 1 o valor de mid não muda e o laço roda para sempre. Para provar o término, mostre uma quantidade que diminui a cada volta e não pode passar de um limite (aqui, hi - lo).

Análise amortizada

Algumas operações são baratas quase sempre e caras de vez em quando. Se olhássemos só a pior operação isolada, seríamos pessimistas demais. A análise amortizada dá o custo médio de uma operação ao longo de uma sequência inteira de operações no pior caso. Não há probabilidade: é uma garantia sobre a sequência.

O vetor dinâmico que dobra

Um vetor dinâmico tem uma capacidade. Acrescentar a um vetor cheio é caro porque todos os elementos são copiados para um vetor novo com o dobro da capacidade. Começando com capacidade 1, após 16 inserções as cópias foram 1 + 2 + 4 + 8 = 15 no total (a 17ª inserção copiaria mais 16). A soma das cópias é sempre menor que 2n, então cada inserção custa O(1) amortizado.

capacidade: 1   2   4       8               16
inserção #: 1   2  3 4,5 ... 8,9 ....... 16,17
cópias:     -   1   2   4              8      (cresce quando cheio)

total de cópias após 16 inserções = 1 + 2 + 4 + 8 = 15

Se, em vez disso, crescermos por uma quantia fixa (digamos +100 posições), as cópias são n + (n-100) + (n-200) + ... que é cerca de n²/200 no total. Isso é Θ(n²) para n inserções, então cada inserção custa O(n) amortizado. Dobrar (crescer por um fator) é o que torna O(1).

O contador binário

Um contador binário inverte bits quando incrementa. O bit mais baixo inverte toda vez, o seguinte a cada 2 incrementos, o seguinte a cada 4... Para um contador de 5 bits incrementado 16 vezes, as inversões são 16 + 8 + 4 + 2 + 1 = 31, menos de 2 por incremento. Então um incremento custa O(1) amortizado, mesmo que um incremento possa inverter todos os bits.

Métodos

• Método agregado: some o custo das n operações e divida por n (o que fizemos acima).
• Método contábil (do banqueiro): cobre um preço fixo de cada operação. As operações baratas são cobradas a mais do que custam, e o extra vai para um banco como crédito. As operações caras são pagas com o crédito. O banco nunca pode ficar negativo.
• Método do potencial: uma versão mais formal da mesma ideia, com uma 'energia potencial' guardada na estrutura de dados.

O limite inferior da ordenação por comparação

Até agora procuramos algoritmos mais rápidos. Agora perguntamos: existe um limite de velocidade que nenhum algoritmo de ordenação consegue vencer? Para algoritmos que ordenam comparando dois itens por vez (como merge sort, quicksort e heap sort), a resposta é sim: Ω(n log n).

A árvore de decisão

Desenhe cada comparação que o algoritmo faz como um ramo: 'a < b?' vai para a esquerda se sim e para a direita se não. Cada caminho da raiz até uma folha é uma execução do algoritmo, e a folha diz qual ordem foi encontrada. Para n itens distintos há n! ordens possíveis, e cada uma precisa aparecer como folha. Então a árvore tem pelo menos n! folhas.

ordenando 3 itens a, b, c  (3! = 6 ordens = 6 folhas)

            a < b ?
          /         \
     b < c ?       a < c ?
     /     \       /     \
  abc    a<c?    bac    b<c?
         /  \           /  \
       acb  cab       bca  cba

Uma árvore binária de altura h tem no máximo 2^h folhas. Então 2^h ≥ n!, e a altura satisfaz h ≥ log₂(n!). A altura é o número de comparações no pior caso. E log₂(n!) = Θ(n log n). Portanto qualquer ordenação por comparação precisa de Ω(n log n) comparações no pior caso.

Para 4 itens: 4! = 24 ordens, e 2⁴ = 16 < 24 ≤ 32 = 2⁵, então são necessárias pelo menos 5 comparações. Para 5 itens: 5! = 120 > 2⁶ = 64, então ninguém ordena 5 itens com 6 comparações no pior caso: tal afirmação não pode ser verdadeira.

Como algumas ordenações podem ser mais rápidas?

O limite vale só para ordenações que descobrem os dados comparando. Ordenações que usam os próprios valores escapam dele:

Eles não contradizem o limite porque nunca perguntam 'a < b?'. Usam o valor como índice numa tabela. O preço: o intervalo k precisa ser pequeno, e só funcionam para coisas como inteiros ou chaves curtas.

Complexidade de espaço

Tempo não é a única coisa que custa. Um algoritmo também usa memória. A complexidade de espaço mede a memória que um algoritmo precisa quando a entrada cresce. Normalmente contamos o espaço auxiliar: a memória extra usada além da própria entrada.

Espaço auxiliar O(1) significa um número fixo de variáveis extras, que não cresce com n. Cuidado: 'no próprio lugar' com recursão ainda usa espaço, porque cada chamada que não terminou fica guardada na pilha de chamadas. Se uma função chama a si mesma n vezes em cadeia, a pilha guarda n chamadas: O(n).

// PT: Cada chamada espera a próxima, então n quadros se empilham: espaço O(n).
// (Sem otimização de chamada em cauda, que a maioria das linguagens não garante.)
function sum(n: number): number {
	if (n === 0) return 0;
	return n + sum(n - 1);
}

O quicksort particiona no próprio lugar, mas recursa nos dois lados. Se o pivô for sempre o pior, a cadeia de chamadas tem profundidade n, então a pilha é O(n). O Fibonacci com duas chamadas faz um número exponencial de chamadas no total, mas em um único momento só um caminho a partir da raiz está aberto, com no máximo n chamadas de profundidade, então a pilha é O(n).

Há também uma ligação com o tempo. Se cada passo toca um número constante de células de memória, um algoritmo não pode usar mais células do que tem passos. Então S(n) = O(T(n)): o espaço nunca é maior que o tempo. O contrário é falso: um algoritmo pode levar muito tempo usando quase nenhuma memória.

Complexidade das operações comuns de estruturas de dados

Escolher uma estrutura de dados é escolher quais operações são baratas. Aqui estão os custos que você deve conhecer, com n elementos.

Vamos ver por que algumas dessas valem.

Vetores e listas encadeadas

Um vetor guarda os itens lado a lado, então a posição i é achada por uma conta simples: O(1). Mas inserir no começo empurra cada item uma casa para a direita: O(n). Uma lista encadeada é uma corrente de caixinhas, cada uma apontando para a próxima, então inserir no começo só muda um ponteiro: O(1). Para chegar à i-ésima caixinha é preciso andar pela corrente: O(n).

Tabelas hash

Uma tabela hash com uma boa função hash e um fator de carga controlado (itens por gaveta) acha uma chave em O(1) em média. Com encadeamento (cada gaveta guarda uma lista), se todas as chaves caírem na mesma gaveta, a busca percorre uma lista de n chaves: O(n) no pior caso.

Árvores e heaps

Uma árvore binária de busca guarda as chaves menores à esquerda e as maiores à direita. Se você inserir 1, 2, 3, ..., n em ordem numa árvore simples sem balanceamento, toda chave vai para a direita e a árvore vira uma lista: buscar n custa O(n). Uma árvore balanceada (AVL, rubro-negra) se conserta sozinha e mantém a altura em O(log n), então dá busca, inserção e remoção em O(log n) no pior caso, e um percurso em ordem lista as chaves ordenadas em O(n). Uma tabela hash não lista chaves em ordem, então só a árvore balanceada atende a todos esses requisitos.

Um min-heap binário mantém o menor item na raiz: lê-lo é O(1), removê-lo é O(log n) (move o último item para a raiz e deixa ele afundar). Construir um heap a partir de um vetor qualquer com sift-down do último nó interno até a raiz custa apenas O(n), não O(n log n), porque a maioria dos nós está perto do fundo e afunda muito pouco.

Uma fila sobre um vetor

Se uma fila é um vetor, enfileirar escreve no fim (O(1) amortizado), mas desenfileirar remove o índice 0 e desloca todos os outros: O(n). Para n enfileiramentos e n desenfileiramentos o total é O(n²). Uma lista encadeada, ou um vetor com dois índices que andam (um buffer circular), leva cada operação a O(1).

P, NP e intratabilidade

Até aqui todo algoritmo que vimos é 'rápido o bastante'. Mas alguns problemas parecem não ter nenhum algoritmo rápido. Para falar deles, cientistas da computação separam os problemas em classes.

Polinomial e não polinomial

Um algoritmo roda em tempo polinomial se seu custo é limitado por n elevado a uma potência fixa: n, n log n, n², n³⁰⁰... Algoritmos como 2ⁿ ou n! não são polinomiais (são exponenciais ou piores). Até n^(log n) não é polinomial. Algoritmos polinomiais são chamados tratáveis (administráveis). Os outros são intratáveis para entradas grandes: nem um computador um milhão de vezes mais rápido salva o 2ⁿ.

As classes

     +--------------------------+
     |           NP             |
     |    +----------+          |
     |    |    P     |   NP-    |
     |    |          | completo |
     |    +----------+          |
     +--------------------------+

  P está dentro de NP.  P = NP?  Ninguém sabe.

Fatos que você precisa

• P ⊆ NP: se você consegue resolver um problema rápido, também consegue verificar uma resposta rápido.
• P = NP é uma questão em aberto. Ninguém provou, e ninguém provou o contrário. A maioria dos especialistas acredita que P ≠ NP, mas isso é uma crença, não um teorema.
• Um problema de decisão tem resposta sim/não. A versão de decisão do caixeiro viajante pergunta: 'existe um roteiro que visita as n cidades uma vez e volta ao início com custo no máximo K?'. Ela está em NP porque, dado um roteiro, você verifica em tempo polinomial que ele visita cada cidade uma vez e que o custo é no máximo K.
• Se alguém achar um algoritmo polinomial para um problema NP-completo (como o SAT, a satisfatibilidade de fórmulas lógicas), então todo problema de NP tem um, e P = NP.
• Para provar que um novo problema X é NP-difícil, pegue um problema A já conhecido como NP-completo e construa uma redução em tempo polinomial de A para X: um jeito rápido de transformar qualquer instância de A numa instância de X com a mesma resposta. Se X fosse fácil, A seria fácil.

Note o sentido da redução: você reduz o problema difícil conhecido ao novo. Fazer ao contrário (do novo para o conhecido) só mostraria que o novo problema não é mais difícil que A, o que não prova nada sobre a dificuldade dele.

Juntando tudo

Todas as ferramentas desta área respondem a uma pergunta: como o custo de um algoritmo cresce com o tamanho da entrada? Veja como as peças se conectam.

Erros comuns

• Achar que Big O dá o tempo em segundos. Ele dá o formato do crescimento.
• Confundir melhor, pior e caso médio com as notações O, Ω e Θ.
• Dizer Θ quando você só provou O.
• Esquecer de descartar constantes e termos menores, ou descartar um termo que importa (por exemplo dentro de um expoente).
• Ignorar a memória usada pela recursão.
• Usar o teorema mestre quando a recorrência não tem a forma a · T(n/b) + f(n).
• Acreditar que um computador mais rápido muda a ordem de crescimento.
• Ler NP como 'não polinomial'.