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).
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:
- 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
.
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.
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.