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:

1. Busca binária: O(log n)
2. Busca linear: O(n)
3. Ordenamento rápido (em inglês, Quick Sort): O(n * log n)
4. Ordenação por seleção (em inglês, Selection Sort): O(n * n)
5. 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