A versão curta é que é um termo nerd da ciência da computação que também se tornou curto o suficiente para que eu gostasse dele como nome de domínio. Apesar do que os outros lhe possam dizer, não é um erro ortográfico de “login”. Também, Itend para pronunciá-lo como “log” seguido pela letra “n”.
A versão longa é que é o termo usado para descrever uma classe de algoritmos altamente eficientes. Se você me dá uma pequena lição…
Time Complexity
Na ciência da computação, os algoritmos são frequentemente comparados pela quantidade de tempo ou memória que eles consomem para realizar uma tarefa. A fim de tornar estas comparações justas e fáceis de entender, nós as analisamos com base na relação entre o tamanho da tarefa e o número de passos necessários para completar a tarefa.
Por exemplo, suponha que você queria uma média de valores numéricos. Para fazer isso, você precisaria somar todos os números, e então dividir pelo número de valores que você tinha. O número de passos está directamente relacionado com o número de valores: se duplicasse o número de valores para a média, esperaria que demorasse o dobro do tempo. Este é um exemplo de complexidade linear: como o número de itens (abreviado como n)cresce, o tempo para completar a tarefa cresce ao mesmo ritmo.
Você certamente pode fazer muito pior do que o tempo linear; muitas tarefas requerem um tempo polinomial ou até exponencial para serem completadas! Ordenar listas de números é um bom exemplo; você deve fazer múltiplas passagens sobre o datato peneirar tudo em uma ordem final.
No entanto, há também alguns algoritmos que são melhores do que o tempo linear. Considere um jogo de adivinhação onde um humano pensa em um número entre um e 100, e o computador tem que adivinhar o que é. Se o computador adivinhar incorrectamente, o humano diz ao computador se a resposta é “superior” ou “inferior” ao palpite. Ao escolher os palpites com cuidado, esta informação permite ao computador eliminar metade dos números restantes com cada palpite (escolhendo sempre um número no meio do conjunto possível de números).
Porque cada palpite divide o conjunto restante de números ao meio, os palpites são compostos pela metade e criam um expoente inverso: alogaritmo. Efectivamente, o número de passos para resolver o problema cresce linearmente à medida que o espaço do problema cresce exponencialmente. Pensando de outra forma, duplicar o tamanho do problema resulta em apenas um único passo adicional (compare isto com um algoritmo linear, onde duplicar o tamanho do problema também duplica o número de passos). Nós abreviamos esta relação como logn, mostrando que como n (o tamanho do problema) fica maior, o número de passos é apenas o logaritmo desse número.
Assim, os algoritmos logarítmicos são altamente eficientes e bem considerados.