94

Em discussões acerca de performance de algoritmos, é muito comum o uso da notação Big O:

O(1), O(n), O(n2)

É fácil encontrar a definição científica desta notação e é fácil encontrar algumas definições mais informais em inglês.

O que eu peço aqui é uma definição informal desta notação, que seja imediatamente útil até mesmo para o menos versado em matemática.

Vou tentar formular um exemplo para trazer a definição do Big O para o âmbito prático:

Estudando as implementações de lista ArrayList e LinkedList (Java), diz-se que uma das diferenças entre elas é que o método ArrayList.get(int index) é O(1) enquanto o método LinkedList.get(int index) é O(n) mas, na prática, o que a notação Big O está indicando neste caso?

É claro que outros exemplos práticos são bem vindos.

7
  • Tenho que confessar que a definição "científica" é a mais simples e precisa que conheço. Qual a dificuldade que você está tendo com ela?
    – hugomg
    Commented 2/04/2015 às 21:44
  • 5
    A pergunta é boa mas não vou me arriscar responder porque não á fácil acertar o alvo dela, o foco dela não é o conteúdo e sim a forma. Para quem não conhece tem uma pergunta famosa no SO sobre isto. E mesmo traduzir uma dessas respostas eu não sei se resolveria. Não sei se esyá tão simples assim: stackoverflow.com/questions/487258/…
    – Maniero
    Commented 2/04/2015 às 21:44
  • Possível é, só não acho que eu deva fazer.
    – Maniero
    Commented 2/04/2015 às 21:57
  • 5
    Relacionado: "O que é a complexidade de um algoritmo?"
    – mgibsonbr
    Commented 2/04/2015 às 22:06
  • 1
    @bigown não vai responder, só porque a pergunta tem quase o seu nome? Commented 7/10/2016 às 20:10

3 Respostas 3

126
+50

Eis uma definição informal (e visual).

A ideia da notação Big-O é descrever o comportamento geral (também chamado de assintótico, pois é o comportamento no limite conforme os dados crescem) do algoritmo em termos do crescimento do número de operações conforme cresce o número de elementos processados (a quantidade de itens é descrita, genericamente, por n).

A ideia é usar a letra O seguida de uma função sobre n que descreva esse crescimento do algoritmo. Quanto mais rapidamente crescer o número de operações para processar os itens, "pior" é o desempenho do algoritmo (pois ele executa mais instruções e, portanto, demora mais - é "mais complexo").

Os gráficos abaixo (recriados rapidamente no Excel) ilustram as curvas de crescimento mais comuns. O primeiro tem uma visão geral, e o segundo é uma visão menor (eixo Y com menos valores) para exibir mais claramente as "melhores" curvas de crescimento: O(1) e O(log n).

inserir a descrição da imagem aqui

inserir a descrição da imagem aqui

Desses gráficos é possível perceber que:

  • Em um algoritmo de complexidade O(n!) (fatorial) o número de instruções executadas cresce muito rapidamente para um pequeno crescimento do número de itens processados. Dentre os ilustrados é o pior comportamento para um algoritmo, pois rapidamente o processamento se torna inviável. É o caso da implementação inocente do Problema do Caixeiro Viajante ou de um algoritmo que gere todas as possíveis permutações de uma lista, por exemplo (fonte desse exemplo).

  • Um algoritmo de complexidade O(2n) (exponencial) também é bem ruim, pois o número de instruções também cresce muito rápidamente (exponencialmente), ainda que numa taxa menor do que o anterior. É o caso de algoritmos que fazem busca em árvores binárias não ordenadas, por exemplo.

  • Um algoritmo de complexidade O(n2) (quadrático) é factível, mas tende a se tornar muito ruim quando a quantidade de dados é suficientemente grande. É o caso de algorítmos que têm dois laços (for) encadeados, como, por exemplo, o processamento de itens em uma matriz bidimensional.

  • Um algoritmo de complexidade O(n log n) (sub-quadrático ou super-linear) é melhor do que o quadrático, sendo geralmente até onde se consegue otimizar algoritmos que são quadráticos em sua implementação mais direta e inocente (naïve). É o caso do algoritmo de ordenação QuickSort, por exemplo (que tem essa complexidade no caso médio, mas que ainda assim é quadrático no pior caso).

  • Um algoritmo de complexidade O(n) (linear) é aquele cujo crescimento no número de operações é diretamente proporcional ao crescimento do número de itens. É o caso de algoritmos de busca em uma matriz unidimensional não ordenada, por exemplo.

  • Um algoritmo de complexidade O(log n) (logaritmo) é aquele cujo crescimento do número de operações é menor do que o do número de itens. É o caso de algoritmos de busca em árvores binárias ordenadas (Binary Search Trees), por exemplo (no caso médio, no pior caso continua sendo linear).

  • Um algoritmo de complexidade O(1) (constante) é aquele em que não há crescimento do número de operações, pois não depende do volume de dados de entrada (n). É o caso do acesso direto a um elemento de uma matriz, por exemplo.

Assim, na sua pergunta final:

o que significa dizer que ArrayList.get(int index) é O(1) enquanto que LinkedList.get(int index) é O(n)?

Pode-se entender o seguinte:

  1. Ambas as estruturas de dados armazenam listas de n elementos, e ambos seus métodos get são usados para acessar um elemento de posição index.
  2. ArrayList.get(int index) tem complexidade O(1) porque provavelmente faz acesso direto à posição de memória do elemento (tal como uma matriz unidimensional via operador []) ou usa uma tabela de dispersão (hash table) para localizá-lo rapidamente. Ou seja, faz o acesso com 1 única operação.
  3. LinkedList.get(int index), por outro lado, precisa navegar item a item a partir do primeiro item para acessar o item desejado. Isso se deve à estrutura de uma lista ligada ter apenas o ponteiro para o primeiro elemento, que aponta para o próximo, e este aponta para o próximo, e assim sucessivamente. Como no pior caso todos os itens precisarão ser acessados (se o item desejado é o último, isto é, index = n), a complexidade do algoritmo é O(n). Ou seja, faz o acesso com n operações.

Comparar as duas estruturas de dados apenas pela complexidade desse método get é errado, pois muito embora o acesso a um item seja mais rápido com a primeira, a exclusão ou adição de um item no meio da lista é mais rápida com a segunda - uma vez que não é necessário copiar/mover n-1 elementos, bastando modificar as ligações (ponteiros) entre os itens. Assim, em geral essa comparação precisa ser efetuada tendo-se em mente o uso mais amplo que certa estrutura de dados terá em outro algoritmo.

A fonte original dos gráficos é o site http://bigocheatsheet.com/, que aliás tem matrizes de comparação da complexidade na notação Big-O de diferentes estruturas de dados e algoritmos.

Nota: Geralmente, ao usar a notação Big-O, refere-se à complexidade do algoritmo em termos do tempo de execução (relacionado ao número de instruções executadas). Mas, essa mesma analogia pode ser efetuada para descrever a complexidade do algoritmo em termos de espaço (como o espaço de armazenamento cresce conforme cresce o número de dados de entrada). No link referenciado acima pode-se perceber, por exemplo, que as matrizes indicam a complexidade em tempo (Time Complexity) e em espaço (Space Complexity) para as estruturas de dados e algoritmos usando a mesma notação.

6
  • 13
    Por isto eu não respondi, como eu poderia concorrer com isto? :) Interessante ter feito dois gráficos porque o primeiro dá uma ideia errada que as complexidades que mais encontramos são muito próximas, mas é um problema de escala visual.
    – Maniero
    Commented 3/04/2015 às 17:18
  • 2
    Muito bem explicado, parabéns pela didática! Commented 17/04/2018 às 1:42
  • 2
    Simplesmente sensacional! Foi o único que me fez entender de uma vez por todas essa bagaça. Commented 17/12/2018 às 0:38
  • 4
    O cara explicou em 5 min de leitura o que o professor na faculdade não explicou em várias aulas... sua explicação, em notação Big-O é O(1), parabéns e obrigado! rs
    – Robson
    Commented 18/03/2019 às 15:01
  • 2
    Explicação excelente. Obrigado, Parabéns! Commented 4/09/2019 às 18:01
21

É meio difícil dar uma resposta informal para este tipo de conteúdo, uma vez que ele requer um conhecimento de limites de funções, mas vou tentar mesmo assim:

Dadas duas funções não negativas f(n) e g(n), cujo n tende ao infinito, dizemos que f = Ο(g), quando, não importando o quanto n cresça, g(n) sempre será maior ou igual a f(n).

Exemplo

Se f(n) = n² e g(n) = n³, para todo n positivo, sempre será maior que , ou seja, f = O(g) ( n² = O(n³) ).

Observações

  • Se f(n) = 3n³ e g(n) = n³ podemos dizer que f(n) = n³ e que f = O(g), pois normalmente as constantes são omitidas.

  • Podemos dizer também que a função g(n) pode ser expressa como o termo de maior potência em n da função f(n), ou seja, se f(n) = n^5 + n^4 + 6, podemos dizer que g(n) = n^5, que é o termo de maior potência em n de f(n) e também podemos dizer que f = O(g), ou seja, n^5 = O(n^5).

Levando para a complexidade de algoritmos:

Se tivermos um array com n elementos e quisermos achar o 3º elemento (n = 3), nós deveríamos percorrermos 3 elementos no vetor até achá-lo, logo, uma função para achar o nésimo elemento do vetor seria A(n) = n, dessa forma, podemos dizer que g(n) = n, o que implica que A = O(g), ou seja, A = O(n).

De maneira geral isto quer dizer que, não importa o tamanho do vetor, o "máximo de operações" que serão realizadas em uma busca no vetor será de ordem n.

Espero ter ajudado e não ter confundido ninguém :p

0
18

Definição em uma frase:

  • Serve para comparar quanto de um recurso é usado por um algoritmo que processa uma coleção, quando o número de elementos dessa coleção tende a ser muito grande.

Analogia com hash-code:

  • Pra quem já ouviu falar em código-hash... Big-O é como se fosse um código-hash ordenável. Dois valores distintos possuem ordenação relativa. Dois valores iguais não possuem ordenação relativa.

Destacando:

  • o recurso medido, geralmente é tempo de CPU ou memória ocupada (ou algo relacionado... tal como número de operações)
  • pode-se medir o Big-O em diferentes circunstâncias: casos mais favorável, casos medianos, casos menos favoráveis
  • a entrada do algoritmo é uma coleção de tamanho variável (com n elementos)
  • a comparação de notações Big-O só é válida para coleções com muitos elementos
  • geralmente algoritmos tentam equilibrar os recursos de tempo de CPU e memória ocupada, então não há algoritmo melhor, e sim mais apropriado para cada situação

Exemplos:

  • O(n) é sempre menor que O(n2), quando n cresce além de um certo valor. Mesmo que se multiplique o primeiro, ainda assim essa afirmação não muda: O(n*10000000) = O(n) < O(n2).

  • Se um algoritmo processa uma coleção usando memória O(n*log(n)) então ela ocupa menos memória que outro algoritmo equivalente que usa O(n). Portanto, se memória for um recurso escaço, é melhor usar o primeiro. Como são equivalentes, provavelmente o primeiro usará mais CPU e o segundo menos.

  • Para poucos elementos (e.g. 10, 100... depende do algoritmo) não é possível usar a notação Big-O para avaliar nada. Nesses casos será preciso analisar o recurso durante a execução. Um algoritmo cujo tempo de CPU seja n2 é mais rápido que um 1000*n até n = 999, que é mais rápido que um O(1) cuja constante é 10.000.000.

  • Não é possível comparar dois algoritmos cujos Big-O sejam iguais. Mais uma vez é necessário ter em mão a fórmula exata, ou medir manualmente. Um algoritmo 10*n é melhor que um 100*n, mas ambos possuem O(n).

  • Tem vezes que se está interessado no pior caso de um algoritmo, que é quando este recebe um input que causa o pior desempenho. Por exemplo, algoritmos amortecidos(em Inglês) usam estratégias de memória para agilizar operações sucessivas... entretanto esses algoritmos apresentam variações que podem se tornar muito ruins, não sendo compatíveis com requisitos de alta-performance. O objetivo nesses algoritmos é melhorar o Big-O do caso mais comum.

  • Outros algoritmos requerem um Big-O constante, para todos os casos. Muito usado na produção de hardwares. Um exemplo muito interessante são as sorting networks: algoritmos de ordenação de O(1) invariáveis.

4
  • E o negativo foi por... ??? Commented 7/04/2015 às 0:31
  • 2
    Redes de ordenação demoram a profundidade do circuito. Normalmente é O(log^2 N), sendo N o tamanho da entrada. Possivelmente a complexidade de passos do hardware seja muito mais rápido do que o de software, por isso a sensação de O(1) Commented 23/01/2018 às 13:09
  • 2
    E sendo chato, a complexidade é dado em relação ao processamento da entrada, não em relação a uma coleção. Mas isso é só pedantismo e chatice minha mesmo Commented 23/01/2018 às 13:11
  • 1
    O(1) das redes de ordenação está mais pro caráter invariável do hardware... não dá para variar N depois de implementado, pelo menos é isso que eu quis dizer. Sobre a coleção, acho que eu quis dizer que é algo de tamanho variável... de fato uma entrada de tamanho variável, tal como uma coleção. Mas nem sei se vale a pena editar. Commented 23/01/2018 às 13:55

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .