Notações Big O e algorítimos
Neste post vamos dar uma olhada em algoritmos de complexidade de tempo, para mais detalhes sobre o tema de complexidade de espaço, há recursos adicionais no final do post
Se você é uma pessoa comum como eu, provavelmente tem uma rotina para o seu dia, passos que segue todos os dias. Algumas pessoas gostam de acordar e tomar uma xícara de café, e outras escovam os dentes logo pela manhã, e depois tomar café da manhã, ir à academia, tomar banho e assim por diante. Então, o que isso tem a ver com algoritmos ou notações Big O? Bem, nada com Big O por enquanto, mas, algoritmos são como nossas rotinas, um conjunto de instruções, falando sobre rotinas de computador, quando você abre o Twitter, por exemplo, eles têm um algoritmo para buscar tendências e o tweets mais quentes, ou quando você pesquisa algo no Google, eles têm um conjunto de instruções para lidar com a sua pesquisa.
Que problema eles resolvem
Eles fazem parte do nosso dia e não necessariamente “resolvem” um problema, mas podemos conseguir o que queremos. Podemos pesquisar por um e-mail usando um algoritmo de pesquisa, podemos encontrar uma pessoa no Instagram pelo nome ou podemos fazer coisas importante como pousar um foguete na lua. Nós usamos algorítimos para cálculos pesados no qual os computadores fazem muito rápido.
O que faz um bom algoritmo
Primeiro, precisamos pensar no que é uma boa solução para você, taxa de assertividade? Rapidez? Normalmente, tendemos a preferir
ambos quando se fala em eficiência de algoritmo, mas especificamente em velocidade, podemos medi-la através do Big O(n). E
antes de você pensar que temos cronômetros apontando para os computadores executando algoritmos diferentes, isso é uma estúpida
maneira de medi-los, porque existem muitos fatores como velocidade do processador, otimização do compilador ou a maneira como a linguagem
de programação foi construída. Em vez disso, temos Big O(n), que mede a velocidade do algoritmo de acordo com o tamanho do
input avaliando seu pior cenário.
Como o tamanho da entrada afeta o desempenho
É inegável que pesquisar em uma lista de 500 mil nomes de pessoas do Facebook é mais pesado que uma lista de 2 mil membros de um grupo de discord. Mas como especificamente isso afeta o algoritmo? Bem, dependendo da sua abordagem, ou o tipo de algoritmo escolhido, o algoritmo pode perder muito tempo pesquisando nomes que não são importantes para a pesquisa, se você pressionar T (20ª letra do alfabeto), por exemplo, a pessoa que você está tentando encontrar é muito mais provável de estar próximo ao final da lista do que ao início e comparando as abordagens de pesquisa linear e binária, podemos dizer com segurança que a busca binária é muito mais rápida que a linear.
Tomando como exemplo uma lista de 500 mil nomes ordenados alfabeticamente e utilizando o algoritmo de pesquisa linear O(n), se
nosso destino é o último nome da lista (pior cenário), precisaríamos passar por 499.999 itens para chegar
nosso alvo. Por exemplo, se fosse 1ms para cada nome que passaríamos, os algoritmos levariam cerca de 8 minutos
para completar a busca, e se usarmos busca binária O(log n), o algoritmo levaria um máximo de 19 tentativas resultando em 19ms
Como posso definir o Big O do meu algoritmo?
Bem, temos muitos artigos e cheatsheets explicando o desempenho de cada algoritmo, mas como eu disse no
parágrafo anterior, a velocidade do seu algoritmo está relacionada ao seu tamanho do seu input, e o n dentro dos parênteses do Big O(n), é a
equação do seu algoritmo. Então, de uma maneira simples de explicar, o n é o tamanho do input multiplicado pelo tempo que cada processo
levaria, mas transformamos em uma expressão: tempo * n. Na busca binária, por exemplo, o
Big O é log n, equação explicada pela seguinte resposta do Stack Overflow
O(log N) basicamente significa que o tempo aumenta linearmente enquanto o n aumenta exponencialmente.
E se eu tiver mais de um tipo de algoritmo?
Como dito anteriormente, Big o assume o pior cenário. Se o Facebook usasse diferentes tipos de algoritmos com base em um "plano" de usário, o algoritmo linear para usuários gratuitos e a busca binária para usuários premium, o pior cenário é a busca linear porque é a mais lenta. Veja o código abaixo.
_6switch (tipoDeUsuario) {_6 caso 'PREMIUM':_6 return buscaBinaria; // O(log n)_6 default:_6 return buscaLinear; // O(n)_6}