Programadores em geral tendem a escrever códigos para funcionar, e está super certo, mas conforme você ganha experiência e entende as diferentes camadas envolvidas no processo você tende a se importar mais com impacto do desempenho de algumas camadas em determinados momentos.
O que é Time Complexity
Time Complexity é sobre a quantidade de operações que um código executa até alcançar o resultado esperado, não é sobre a duração em tempo como milissegundos, segundos, minutos, etc.
Veja os exemplos abaixo.
void PrintOddNumberV1()
{
for (var i = 1; i <= 10; i++)
{
if (i % 2 == 0)
Console.WriteLine(i);
}
}
void PrintOddNumberV2()
{
for (var i = 2; i <= 10; i+=2)
{
if (i % 2 == 0)
Console.WriteLine(i);
}
}
Você sabe dizer qual dos dois códigos é mais rápido ?
O método PrintOddNumberV2 é 50% mais rápido do que PrintOddNumberV1 porque ele pula os números que se sabe que não são pares, ele incrementa de 2 em 2. A questão nesse exemplo é de "porquê vou gastar tempo e recurso com algo que sei que não vou usar"
Porque é importante
Conforme se ganha experiência é interessante começar a se preocupar em custos, e no caso desse tema a velocidade, e Time Complexity é sobre isso e muito mais.
Além do código funcionar, é interessante saber utilizar estruturas e truques que melhoram a velocidade do código.
Existem alguns tipos e cada um é bom para determinado cenário, por mais que não pareça.
Diferentes Notações
As notações são utilizada para expressar o limite de uma função, podendo ser o melhor, médio ou pior caso dela.
Os diferentes tipos são:
- Big O
- Big Omega
- Big Theta
Suas categorias mais conhecidas são:
- Constante O(1)
- Linear O(N)
- Logarítmica O(log N)
- Quadrática O(N^2)
- Exponencial O(2^N, 3^N, etc)
- Fatorial O(N!)
Por exemplo, uma função de busca binária executa no seu pior caso em O(log N), mas não significa que será em todos os casos, se a busca binária encontrar o valor na primeira tentativa então foi executada em O(1), que é seu melhor caso.
Big O
Big O é a notação utilizada para expressar o limite de uma função, entenda como o pior caso ou o mais demorado que um algoritmo pode executar.
A notação Big O normalmente considera o pior caso possível, por mais que o valor seja encontrado na primeira tentativa, deve-se considerar o pior.
Essa é a notação mais utilizada para expressar o desempenho de um algoritmo.
Para pronunciar a notação de Big O normalmente é falado "O de + o tipo". Exemplo "O de log de N" ou "Ordem de log de N".
Big Omega
Ao contrário do Big O, Big Omega expressa o melhor caso ou o mais rápido que um algoritmo pode executar. Pode-se dizer que é o tempo mínimo para executar um algoritmo.
Big Theta
Big Theta expressa a complexidade média de execução de um algoritmo, mas não é algo como a média aritmética
Básicamente o que procuramos é saber a média de execução de um algoritmo, porque é o que mais vai acontecer.
Categorias
As categorias descrevem a eficiência de um algoritmo.
Constante - O(1)
Esse é o melhor cenário possível para um código executar, porque ele vai direto na posição informada e se for uma sequência ele não se importa com o tamanho se ela tem o tamanho de 1 elemento ou de 1 bilhão de elementos. Isso significa que não é feito uma busca até achar o valor, porque já se sabe a posição que o valor está e sempre vai acessar direto sem acessar as outras posições.
Se tiver um sequência ela não precisa estar ordenada.
Onde é utilizado:
- Atribuir um valor para uma variável;
- Acessar ou atribuir um valor no array pelo seu índice;
Exemplo 1:
int valor = 5; // Atribui um valor para a variável
int indice = 2;
someArray[indice] = "ola mundo"; // Atribui um valor em uma posição no array
Exemplo 2:
Aqui tem um array qualquer com alguns valores escondidos com “?”
array [?, ?, ?, ?, ?]
O símbolo de “?” nesse exemplo significa que não se conhece o valor até acessar a posição.
array[2] = "olá mundo"; // Insere um valor em uma posição
resultado que se conhece do array será [?, ?, "olá mundo", ?, ?] visto que só foi acessada a posição 2.
var value = array[2]; // Acessa um valor por sua posição
Se um algoritmo, que por exemplo, sempre executa em 3 passos, independente do tamanho da sequência, que pode ter 1 elemento ou 1 bilhão de elementos, você pensaria que ele é O(3), mas está errado, na verdade ele é O(1) porque ele se mantém constante independente do tamanho da sequência.
Veja o exemplo abaixo.
Console.WriteLine("Ola Mundo");
Console.WriteLine("Ola Mundo");
Console.WriteLine("Ola Mundo");
Linear - O(N)
Quando não se sabe a posição de um valor e tem que procurar em toda a sequência, sem pular posições, considerando que o valor pode ser encontrado na primeira O(1) ou última posição O(N), ou mesmo não existindo na sequência. Sempre assuma o pior cenário, que é o tamanho da sequência, no caso N.
O tempo de execução é proporcional ao tamanho da sequência informada.
Aqui é feito um incremento de forma constante, um exemplo é quando você incrementa um loop sempre em +1, +5 ou +20… +x, etc.
A sequência não precisa estar ordenada.
Onde é utilizado:
- Loops como while, for, foreach, LinkedList, etc.
// N é o tamanho da sequência e é incrementado o loop em 3
for (var i = 0; i < N; i += 3)
{
// code
}
De qualquer forma, se você não sabe onde está o valor, assuma o pior caso possível, que é o tamanho da sequência.
Logarítmica - O(log N)
É uma das melhores funções para encontrar um valor em uma sequência porque a quantidade de iterações está no resultado de Log(N) da sequência e não precisa acessar todas as posições para descobrir onde está o valor que procura. O Tamanho da sequência pouco afeta o desempenho porque a quantidade de operações não é proporcional ao tamanho da sequência.
Enquanto um algoritmo usando O(N) leva muitos passos para até o fim, o O(log N) incrementa em um passo cada vez que a quantidade de elementos dobra.
Por exemplo, um array com 8 elementos leva 3 passos, um array com 16 elementos leva 4 passos e assim sucessivamente.
A eficacia do logaritmo é tão boa, que se quiser percorrer uma lista com 1 milhão de elementos será preciso iterar, no pior caso, 19 vezes e não N vezes que é o tamanho da lista.
Para funcionar corretamente a sequência precisa estar ordenada.
Onde é utilizado:
- Busca binária
for (var i = 1; i <= 1_000_000; i *= 2)
{
// code
}
Quadrática - O(N^2)
Nesse cenário, a potência significa, geralmente, que existe loop dentro de outro loop usando a mesma sequência.
A sequência não precisa estar ordenada.
Onde é utilizado:
- Verificar valores duplicados (existem outros algoritmos melhores para isso)
- Processamento de uma matriz bidimensional
for (var i = 0; i < N; i++)
{
for (var j = 0; j < N; j++)
{
// code
}
}
Como medir
Bem, não é algo tão fácil assim para alguns casos, mas também nada tão difícil. Abaixo existem algumas questões para se levar em consideração.
-
Ignore valores constantes como exemplo N + 4, log 2(N), N*5, 100N, N^2 + 10, N / 2, etc.
-
Considere a maior ordem(pior caso) se tiver mais de uma. Exemplo: N^4 + N^3 + N^2 + N^1 considera apenas a maior, no caso N^4 que fica O(N^4)
Você vai perceber que existente algoritmos que têm a mesma categoria de Big O mas tem desempenho muito diferentes, como no caso do Bubble sort e Selection sort, ambos são O(N^2), mas o Selection sort executa 2x mais rápido que o Bubble sort, isso porque o Selection sort é O(N^2 / 2) e o Bubble sort é O(N^2).
Outro exemplo de quando ignora valores constantes é um algoritmo para contar os números pares. Se verificar todas as posições da sequência será um O(N) mas se pular os números de 2 em 2, ignorando os números impares, será um O(N / 2).
Ao ignorar valores constantes percebe-se que pode ser difícil de escolher o melhor algoritmo por causa dos valores constantes que foram escondidos, nesse caso tem que ser feito análise e testes com o algoritmo.
Conclusão
Como visto você deve se importar com o desempenho do seu código, mas sempre ponderando no seu custo e benefício geral para otimizar e manter.
Um algoritmo que é O(N^2) é considerado lento, mas para determinados casos é o melhor que se pode fazer para resolver o problema. Mas às vezes alterar um algoritmo de O(N^3) para O(N^2) já é uma grande vitória porque o código já melhora exponencialmente.
Quando encontrar dois algoritmos com a mesma notação será necessário fazer uma análise teórica e prática.
Abaixo é o gráfico sobre as notações Big O.
