Notação do big-O

Os algoritmos são a base para o funcionamento de qualquer dispositivo digital. Hoje, a programação possui diversos tipos de linguagens, com suas respectivas vantagens.

É notável o avanço da tecnologia, principalmente na área de computação. Computadores com alta capacidade de armazenamento e processamento abriram portas para novas tecnologias como BigData e Deep Learning.

Entretanto, por mais que as máquinas tenham se tornado mais poderosas, a importância do bom funcionamento do algoritmo sempre foi requerido.

Um algoritmo bem programado pode consumir bem menos memória, evitando uso excessivo do CPU e oferecendo uma experiência melhor ao usuário.

Mas na programação, o cenário mais importante é o pior cenário, pois a disponibilidade é um fator indispensável na segurança da informação.

Um método bastante utilizado ao redor do mundo para medir a disponibilidade de um serviço é a notação big-O.

O que é a notação big-O?

Esse método também é chamado de notação O grande.

Notação big-O é um método utilizado para medir a eficiência de um algoritmo de forma simples e prática.

Esse método usa os dados de entrada como base para calcular o tempo de processamento de um algoritmo. Quanto mais dados de entrada a serem processados, mais uma máquina tende a demorar até chegar ao resultado final.

Pior cenário possível

A notação big-O é usada para medir o tempo de processamento de um algoritmo, porém o pior cenário possível é o cenário que mais importa aos programadores.

Caso uma máquina chegar ao seu limite de processamento devido a um algoritmo mal implementado, isso pode trazer sérias consequências ao funcionamento, prejudicando principalmente a disponibilidade do serviço.

Por que usar a notação big-O?

Obviamente, conforme o número de dados de entrada aumenta, o tempo de processamento da máquina também aumenta. A notação big-O ajuda a analisar se uma máquina mediana suporta ou não o algoritmo no pior cenário possível.

É certo que dependendo da eficiência da máquina, o resultado pode ser diferente. Porém, o principal foco desse método é a eficiência do algoritmo independente da eficiência da máquina.

Como se avalia um algoritmo na notação big-O?

A notação do O grande é uma notação assintótica, que utiliza termos para classificar o algoritmo.

Observa-se no gráfico acima, a diferença no tempo de processamento (eixo Y) conforme a quantidade de dados de entrada aumenta (eixo X).

Como se aplica a notação big-O na prática?

Esse método possui duas regras básicas:

1. Os termos maiores são dominantes, portanto os termos considerados menores são omitidos
2. Constantes também são ignoradas

1. Os termos maiores são dominantes

A porção do algoritmo com maior custo de tempo de processamento torna-se o resultado final.

A ordem dos termos são:
O(1) < O(log n) < O( Sqrt(n) ) < O(n) < O(n log n) < O(n^2) < O(n^3) < O(2^n)

Se um algoritmo possui uma porção O(1) e outra O(n), temos a conta abaixo:
$$O(1) + O(n)$$

Porém, nesse exemplo o termo dominante é o termo com a pior performance, portanto teremos como resultado final apenas:
$$O(n)$$

Outros exemplos:
$$O(n) + O(n^2) = O(n^2) \\ O(1) + O(n) + O(n) = O(n) \\ O(1) + O(n) + O(n^2) = O(n^2)$$

2. Constantes também são ignoradas

Algoritmos contendo múltiplas porções com mesmo custo de processamento, não se repetem.

O exemplo abaixo não é correto:
$$O(1) + O(1) = 2 * O(1)$$

A constante deve ser omitida, reproduzindo o resultado abaixo:
$$O(1)$$

Como implementar a notação O grande baseando-se no algoritmo?

Considere o seguinte algoritmo:

function calcular() {
    return 15 * (30 + 90);
}

print(calcular());

O exemplo de algoritmo acima apenas realiza um pequeno cálculo. No caso acima, não há repetições, portanto o tempo de demora é representado como O(1).

Como calcular repetições dentro do algoritmo?

Ao utilizarmos loops dentro do algoritmo o resultado pode variar um pouco:

function calcular(int $no) {
	return 15 * ($no + 90);
}

foreach ($i = 0; $i < 1000; i++) {
	print(calcular($i));
}

No exemplo acima, temos um loop com 1000 repetições. Nesse caso podemos fazer a seguinte afirmação:
$$O(1) * O(1000) = O(1000)$$
Porém, na notação do O grande, não se escreve dessa maneira uma vez que precisamos analisar os dados de entrada. Por isso, devemos escrever da seguinte forma:
$$O(1) * O(n) = O(n)$$

Como calcular repetições de repetições dentro do algoritmo?

Quando temos um loop dentro do outro, temos repetições de repetições:

function calcular(int $no1, int $no2) {
	return 15 * ($no1 + $no2);
}

foreach ($i = 0; $i < 1000; i++) {
	foreach ($j = 0; $j < 1000; j++) {
		print(calcular($i, $j));
	}
}

No algoritmo acima, o número de processos é elevado ao quadrado:

$$O(n^2)$$

Assim como no algoritmo abaixo, o número de processos é elevado a 3:

function calcular(int $no1, int $no2, int $no3) {
	return $no3 * ($no1 + $no2);
}

foreach ($i = 0; $i < 1000; i++) {
	foreach ($j = 0; $j < 1000; j++) {
		foreach ($k = 0; $k < 1000; k++) {
			print(calcular($i, $j, $k));
		}
	}
}

Resultado:
$$O(n^3)$$

O que fazer para melhorar o algoritmo, caso ele seja classificado com alto custo de processamento?

Em alguns casos, não há como evitar o alto custo de processamento. Porém, geralmente é possível otimizar esses processos utilizando técnicas de programação adequadas. Alguns exemplos disso são:

• Otimização de processamento de tempo envolvendo estrutura de dados
• Substituindo buscas lineares

Otimizando a estrutura de dados

Um bom exemplo de otimização de algoritmos é a utilização de estruturas de dados de modo apropriado, como por exemplo a pilha e a fila.

Se compararmos com o arranjo (array), temos a seguinte tabela:

+--------------------+---------------------------------------------------------------------------+
| Estrutura de dados |                           Complexidade temporal                           |
|                    +-------------------------------------+-------------------------------------+
|                    | Cenário intermediário               | Pior cenário                        |
|                    +--------+-------+----------+---------+--------+-------+----------+---------+
|                    | Acesso | Busca | Inserção | Remoção | Acesso | Busca | Inserção | Remoção |
+--------------------+--------+-------+----------+---------+--------+-------+----------+---------+
| Arranjo (Array)    | O(1)   | O(n)  | O(n)     | O(n)    | O(1)   | O(n)  | O(n)     | O(n)    |
+--------------------+--------+-------+----------+---------+--------+-------+----------+---------+
| Stack (Pilha)      | O(n)   | O(n)  | O(1)     | O(1)    | O(n)   | O(n)  | O(1)     | O(1)    |
+--------------------+--------+-------+----------+---------+--------+-------+----------+---------+
| Queue (Fila)       | O(n)   | O(n)  | O(1)     | O(1)    | O(n)   | O(n)  | O(1)     | O(1)    |
+--------------------+--------+-------+----------+---------+--------+-------+----------+---------+

Observando a tabela acima, podemos chegar a conclusão que a utilização de arranjos (array) para acessar dados em uma estrutura de dados é potencialmente mais efetivo do que a pilha e a fila, mesmo no pior dos casos.

Porém, na inserção e remoção de dados de uma estrutura, a pilha e a fila são muito mais eficientes do que o arranjo.

Ao utilizar os pontos fortes de estruturas em cenários apropriados, pode-se obter melhores resultados.

Substituindo buscas lineares por buscas binárias

A busca linear é um algoritmo sequencial, também considerado um algoritmo de força bruta. Algoritmos que utilizam a força bruta, terão sua performance prejudicada caso um grande número de dados de entrada seja utilizado.

A busca linear é um algoritmo que dividi os dados de entrada até encontrar o valor procurado. Dividir os dados pela metade até encontrar o elemento alvo é uma excelente abordagem para melhorar o tempo de processamento.

Conclusão

A notação do O grande é um método de fácil implementação, usado para avaliar a eficiência de um algoritmo em relação ao tempo de processamento.

Esse método é de extrema utilidade quando analisamos o pior cenário possível, no qual uma enorme quantidade de dados seriam passados como entrada.

Ao analisar o pior cenário, é possível chegar a conclusão da necessidade ou não da otimização de um algoritmo.