Artigo original: An Introduction to the Time Complexity of Algorithms
Na ciência da computação, análise de algoritmos é uma parte fundamental. É importante encontrar o algoritmo mais eficiente para a resolução de um problema. É possível que muitos algoritmos sejam capazes de resolver um problema, mas o desafio, aqui, é escolher o mais eficiente.
O ponto agora é: como vamos reconhecer o mais eficiente se temos um grupo com diversos algoritmos? Aqui, o conceito de complexidade de tempo e de espaço dos algoritmos ganha vida. A complexidade de tempo e a de espaço agem como uma medida escalonável para algoritmos. Comparamos os algoritmos com base na sua complexidade de espaço (total de memória) e de tempo (número de operações).
O valor total de memória do computador usada por um algoritmo quando executado é a complexidade de espaço daquele algoritmo. Para deixar este artigo um pouco menor, não discutiremos esse tipo de complexidade aqui.
Complexidade de tempo
Complexidade de tempo é o numero de operações que um algoritmo necessita para completar seu objetivo (considerando que cada operação leva o mesmo tanto de tempo). O algoritmo que executa a tarefa no menor número de operações possível é considerado o mais eficiente em termos de complexidade de tempo. Entretanto, as complexidades de tempo e de espaço também são afetadas por fatores como seu sistema operacional e hardware, mas não incluiremos isso nessa discussão.
Agora, para entender a complexidade de tempo, veremos um exemplo em que comparamos dois algoritmos diferentes que foram usados para resolver um problema específico.
O problema é a busca. Temos que buscar por um elemento em um array (nesse problema, assumiremos que o array está ordenado em ordem ascendente). Para resolver esse problema, temos dois algoritmos:
1. a busca linear (em inglês, linear search)
2. a busca binária (em inglês, binary search)
Vamos assumir que o array contém dez elementos e temos que encontrar o número 10 no array.
const array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
const buscar_elemento = 10;O algoritmo de busca linear compara cada elemento no array com a variável buscar_elemento. Quando o encontra dentro do array, retorna true.
Agora, vamos contar o número de operações necessárias. Aqui, a resposta é 10 (visto que compara cada elemento do array). Então, a busca linear usa dez operações para encontrar o elemento desejado (este é o número máximo de operações para esse array; no caso da busca linear, também é considerado o pior caso para um algoritmo).
Em geral, a busca linear necessitará de um número n de operações no seu pior caso (onde n é o tamanho do array).
Vamos examinar o algoritmo de busca binária para esse caso.
A busca binária pode ser facilmente entendida nesse exemplo:
Se estivermos tentando aplicar essa lógica no nosso problema, primeiro comparamos buscar_elemento com o elemento do meio do array, que é 5. Agora visto que 5 é menor que 10, começaremos a procurar por buscar_elemento no array de elementos maiores do que 5, e continuaremos assim até encontrar o desejado elemento – que, neste caso, é 10.
Agora, tente contar o número de operações de busca binária necessários para encontrar o elemento desejado. Levou, aproximadamente, quatro operações. Esse foi o pior caso para a busca binária. Isso mostra que existe uma relação logarítmica entre o número de operações necessárias e o tamanho total do array.
número de operações = log(10) = 4 na base 2 (aproximadamente)
Podemos generalizar esse resultado para a busca binária:
Para um array de tamanho n, o número de operações executadas pela busca binária é log(n)
Notação Big O
Nas declarações acima, vimos que, para um array de tamanho n, a busca linear executará n operações para completar a busca. Em contrapartida, a busca binária executou log(n) operações. Para isso, consideramos os respectivos piores casos. Podemos representar isso através de um gráfico (onde o eixo x é o número de elementos do array e o eixo y é o número de operações).
É bem claro pela figura que a taxa na qual a complexidade aumenta para a busca linear é muito mais alta que para a busca binária.
Quando analisamos um algoritmo, usamos uma notação para representar sua complexidade de tempo – essa notação se chama Big O.
Por exemplo: a complexidade de tempo para a busca linear pode ser representada como O(n). Para a busca binária, temos O(log n). Consideraremos que n e log(n) são o número de operações para cada tipo de busca.
A complexidade de tempo (ou notação Big O) para alguns dos algoritmos populares está listada abaixo:
- Busca binária: O(log n)
- Busca linear: O(n)
- Ordenamento rápido (em inglês, Quick Sort): O(n * log n)
- Ordenação por seleção (em inglês, Selection Sort): O(n * n)
- Algoritmo do caixeiro viajante (em inglês, Travelling salesperson): O(n!)
Conclusão
Parabéns se você chegou até este ponto do artigo. Agora, você pode estar se perguntando: porque a complexidade de tempo é tão importante de entender?
Sabemos que, para um número pequeno de elementos (digamos que 10), a diferença entre o número de operações realizadas pela busca binária e pela busca linear não é tão grande, No mundo real, porém, na maioria das vezes, lidamos com problemas que tem um grande volume de dados.
Por exemplo, se tivermos 4 bilhões de elementos usando a busca linear, então, no pior dos casos faremos 4 bilhões de operações para completar a tarefa. A busca binária completará a tarefa em apenas 32 operações. É uma diferença enorme! Agora, vamos assumir que, se uma operação leva 1 ms para completar, a busca binária levará apenas 32 ms enquanto a busca linear levará 4 bilhões de milissegundos (aproximadamente, 46 dias). É uma diferença realmente significativa.
Esse é o motivo pelo qual o estudo da complexidade de tempo se torna importante quando falamos de um grande volume de dados.
Recursos (em inglês)
Grokking Algorithms – escrito por Aditya Y Bhargava
Introduction to Big O notation and Time Complexity – vídeo do CS Dojo