A complexidade de um algoritmo tem a ver com quanto tempo e memória esse algoritmo gasta de acordo com o tamanho de sua entrada. Por exemplo, queremos responder a perguntas como “se meu algoritmo gasta 1 minuto para processar uma entrada de 1000 bytes, quantos minutos ele gastará para processar uma entrada de 2000 bytes?”

Uma maneira muito direta de calcular a complexidade seria encontrando alguma fórmula que dê o número exato de operações feitas pelo algoritmo para chegar no resultado, em função do tamanho da entrada. Por exemplo, no algoritmo

 for(i=0; i<N; i++){
     print(i);
 }

poderíamos dizer que o tempo gasto é

 T(N) =
    N*(tempo gasto por uma comparação entre i e N) +
    N*(tempo gasto para incrementar i) +
    N*(tempo gasto por um print)

No entanto, dá muito trabalho fazer uma conta super precisa dessas e geralmente nem vale a pena. Por exemplo, suponha que tenhamos nos esforçado bastante e descoberto que um certo algoritmo gasta tempo

 T(N) = 10*N² + 137*N + 15

Nesse caso o termo quadrático 10*N² é mais importante que os outros pois para praticamente qualquer valor de N ele irá dominar o total da soma. A partir de N ≥ 14 o termo quadrático já é responsável pela maioria do tempo de execução e para N > 1000 ele já é responsável por mais de 99%. Para fins de estimativa poderíamos simplificar a fórmula para T(N) = 10*N² sem perder muita coisa.

Outro ponto em que podemos simplificar a nossa fórmula é o fator constante multiplicando o N². Para prever o quão rápido o tempo de execução cresce dependendo da entrada não importa se T(N) = 10*N ou T(N) = 1000*N; em ambos os casos dobrar o N vai quadruplicar o tempo de execução.

Por isso tudo, a forma mais popular de se trabalhar com complexidade de tempo e espaço na análise de algoritmos é a complexidade assintótica, que ignora esses fatores constantes e os termos que crescem mais devagar. É agora que entra a história de O-grande, Θ-grande e Ω-grande: essas são notações que usamos para caracterizar uma complexidade assintótica.

Vamos começar pelo O-grande, que é uma maneira de dar um limite superior para o tempo gasto por um algoritmo. O(g) descreve a classe de funções que crescem no máximo tão rápido quanto a função g e quando falamos que f ∈ O(g) queremos dizer que g cresce pelo menos tão rápido quanto f. Formalmente:

Dadas duas funções f e g, dizemos que f ∈ O(g) se existem constantes x0 e c tal que para todo x > x0 vale f(x) < c*g(x)

Nessa definição, a constante c nos dá margem para ignorar fatores constantes (o que nos permite dizer que 10*N é O(N)) e a constante x0 diz que só nos importamos para o comportamento de f e g quando o N for grande e os termos que crescem mais rápido dominem o valor total.

Para um exemplo concreto, considere aquela função de tempo f(n) = 10N^2 + 137N + 15 de antes. Podemos dizer que o crescimento dela é quadrático:

Podemos dizer que f ∈ O(N²), já que para c = 11 e N > 137 vale

10*N² + 137*N + 15 < c * N^2

Podemos escolher outros valores para c e x0, como por exemplo c = 1000 e N > 1000 (que deixam a conta bem óbvia). O valor exato desses pares não importa, o que importa é poder se convencer de que pelo menos um deles exista.

Na direção oposta do O-grande temos o Ω-grande, que é para limites inferiores. Quando falamos que f é Ω(g), estamos dizendo que f cresce pelo menos tão rápido quanto g. No nosso exemplo recorrente, também podemos dizer que f(n) cresce tão rápido quanto uma função quadrática:

Podemos dizer que f é Ω(N²), já que para c = 1 e N > 0 vale

10*N² + 137*N + 15 > c*N^2

Finalmente, o Θ-grande tem a ver com aproximações justas, quando o f e o g crescem no mesmo ritmo (exceto por um possível fator constante). A diferença do Θ-grande para o O-grande e o Ω-grande é que estes admitem aproximações folgadas, (por exemplo, N² ∈ O(N³)) em que uma das funções cresce muito mais rápida que a outra.

Dentre essas três notações, a mais comum de se ver é a do O-grande. Normalmente as análises de complexidade se preocupam apenas com o tempo de execução no pior caso então o limite superior dado pelo O-grande é suficiente.

Complexidade de algorítimo

Mas é importante sinalizar que a definição mais teórica raramente é usada de fato no “mundo real”, mesmo que alguém insista que é um erro, não deixa de ser um fato que é como demonstro abaixo que as pessoas interpretam estes conceitos e esta forma funciona para a maioria dos casos. Estou respondendo porque o assunto é importante para todos e também precisa estar mais acessível. De nada adianta uma informação correta quando uma pessoa não consegue entendê-la.

Aproveite para ter em seu bookmark uma tabela de complexidades.

Definição

Complexidade de algoritmo é a quantidade de trabalho necessário para executar uma tarefa. Isto é medido em cima das funções fundamentais que o algoritmo é capaz de fazer (acesso, inserção, remoção, são exemplos mais comuns em computação), o volume de dados (quantidade de elementos a processar), e é claro, a maneira como ele chega no resultado.

Esta quantidade de trabalho tem a ver com tempo mas também pode referir-se à quantidade de memória necessária para garantir sua execução.

Você pode comparar diferentes grandezas. Você estabelece a complexidade medindo como o algoritmo se comporta quando ele precisa manipular, por exemplo, 10, 100 e 1000 elementos. Se ele consegue fazer em uma operação nos três casos, o algoritmo é constante, se cada um precisa 10 vezes mais operações ele é linear e se preciso do quadrado do número de elementos, obviamente é quadrático. Lembro que são apenas alguns exemplos ilustrativos. Não é difícil notar como isto pode fazer uma enorme diferença de desempenho se você tem grandes volumes de dados. Em algoritmos de altíssima complexidade até pequenos volumes podem ter um desempenho bastante ruim.

Eu achei esta resposta no SO que me pareceu bem precisa e informa bem o que é mais importante sobre o assunto. Como demonstrado nela os termos mais corretos e que muda também a percepção do que seja a informação são limite superior e limite inferior, que efetivamente não são apenas sinônimos para pior e melhor caso.

Em tese qualquer fórmula pode estar dentro da notação Big O ou Big Omega ou Big Theta, mas algumas são mais comuns.

O Big-O é o mais usado, mesmo que de forma ingênua. Veja na Wikipedia as fórmulas mais comuns. Eu destacaria como principais: constante (um if é um exemplo de algoritmo constante, um array e um hash ou dicionário é um exemplo de estrutura de dados que possui acesso constante), logarítmica (busca binária é o melhor exemplo), linear (um for simples, uma lista ligada na maioria das implementações são exemplos) e quadrática ou exponencial (fors aninhados).

Você não pode medir coisas distintas para compará-las. Não pode comparar uma operação de adição numérica com uma ordenação de uma lista.

Costumamos nos referenciar ao Big O como o pior caso e ainda mais raramente Big Omega como o melhor caso (normalmente não é uma informação relevante). E ainda ao Big Theta quando os anteriores se confundem.

Uso trivial

Esta seção não deve ser levada muito ao pé da letra, ela não tem uma base teórica forte, é só uma forma para facilitar o entendimento por quem não tem estudo formal sobre o assunto e deseja ter um pássaro na mão. Estou fazendo simplificações. Não há espaço para explicar todos os detalhes a variações. Pincei alguns aspectos apenas.

Big-O

É muito comum chamar de Big-O quando a informação é sobre a média de execução, mesmo que isto não seja a definição mais precisa para ele. É comum também fazer aproximações ou desconsiderar casos excepcionais. Por exemplo, um hash costuma ter o pior caso como O(n), mas em geral é dito que ele tem O(1) porque isto é o que geralmente acontece. O O(n) acontece apenas em casos extremos.

Em muitos casos é melhor ater-se ao caso médio ainda que seria importante saber antes se realmente há boa distribuição para garantir que a média ocorra na prática. Então o mais comum é usarmos o caso típico como referência e não o pior caso.

Velocidade real

Outro ponto importante é que isto não é uma medida de velocidade real do algoritmo, isto depende de fatores práticos que podem variar de maneira que não é possível especificar formalmente. Esta variação pode ocorrer em função da implementação específica do algoritmo e/ou arquitetura onde está sendo executado (veja um relato de caso real no comentário abaixo do mgibsonbr), conjunto e capacidade das instruções do processador, predição de branch, re-ordem de execução, cache, localidade, custo de administração de outras operações e outros fatores mais “exotéricos” (difíceis de determinar de antemão como necessidade de swap em disco, concorrência e falhas) podem fazer um algoritmo se comportar de forma mais ou menos eficiente em termos de velocidade real. Em teoria estas coisas não existem. Na prática…

Então, em tese e em alguns casos na prática, um O(1) pode ser mais lento que um O(n) ou mesmo um O(n^m), embora neste último seria bem raro. Se esta única operação necessária para um algoritmo constante demora 100ns e a operação individual do algoritmo que tem complexidade O(n^m) demora 10ns com N e M valendo 2, fica claro que o segundo algoritmo irá executar mais rápido, neste raro caso. A grandeza dos dados faz com que a curva de execução não se distancie suficientemente para fazer diferença.

Contra-intuição

Mas é mais comum você ter um O(log n) mais rápido que um O(n) mesmo para um volume de dados maior, afinal o logaritmo costuma se aproximar de números baixos. Mas é claro que pode não valer nada disto pelos fatores acima. O algoritmo O(log n) costuma ter problema de localidade de referência então o O(n) acaba sendo mais rápido em muitos casos.

Olhando um outro aspecto um O(1) pode ser mais lento em alguns casos que um O(log n) ou mesmo complexidades maiores como O(n). Pode parecer estranho que um O(1) possa ser mais lento, mas é normal porque este número indica a quantidade de operações necessárias para se alcançar um resultado. Não fala sobre o tamanho desta operação, quanto tempo a operação individual leva para executar. O hugomg fez uma objeção a isto nos comentários. Eu concordo com ele que isto está errado, mas precisa avisar todo mundo disto. As pessoas fazem aproximações já que elas são suficientes para entender onde se vai chegar na maioria dos casos. Um O(1) pode levar 100ns para achar um item em uma estrutura de dados e um O(n), onde N é 5 pode levar só 50ns se cada operação demora 10ns. Está errado? Pode ser mas é assim que as pessoas usam na prática. É assim que os algoritmos costumam ser divulgados na audiência geral. E sim, sempre aparece alguém contestando esses números porque eles não são bem o que a teoria define.

Existe ainda uma outra variável. Imagina que para calcular um valor hash de uma string você tem que percorrer todos os caracteres desta string. Fica óbvio que o cálculo de um hash individual provavelmente tem complexidade O(n), mesmo que a coleção em que o hash será usado como chave possa ser localizar um item com complexidade O(1).

No caso de uma coleção de hashs não há garantia que o acesso seja feito em O(1). Se houver colisão destes hashs, pelo menos parcialmente a coleção passa procurar com complexidade O(n). Mas é um exagero dizer que a coleção tem complexidade O(n) por causa disto, na prática nunca atingirá esta complexidade no todo. E pode ser que alguma otimização específica consiga que esta procura seja melhor que O(n).

Viu como é complexo determinar complexidade? (pun intended… or not)

Para entender como pode ser ruim em linguagem simples:

O(1) = O(yeah) - constante
O(log n) = O(nice) - logarítmica
O(n) = O(k) - linear
O(n log n) = O(k-ish) - logarítmica linear
O(n^2) = O(my) - quadrática
O(2^n) = O(no) - subexponencial
O(n^n) = O(fuck) - exponencial
O(n!) = O(mg!) - fatorial

Existem diversas outras, essas são as mais comuns, espero que as últimas bem pouco comuns.

Referências externas

• Como calcular
• Um pouco de teoria.
• E em português.

Leia também: