Complexidade Logarítmica O(log n)

#bigonotation #algorithms #computerscience

Back to school, vamos falar de matemática mas é algo tão simples que nem vai da tempo de você fica chateado.

É necessário entender um pouco sobre Logaritmos para entender a próxima notação, basicamente o que você precisa ter em mente é que logaritmos são o inverso de exponenciais.

E talvez você esteja lendo isso e “eu já vi isso na faculdade e etc”, eu não vi isso na faculdade porque eu não fiz faculdade eu tenho estudado isso por conta própria.

Se você também tá estudando por conta própria e acha que saber sobre complexidade, estrutura de dados não vai fazer diferença eu tomaria mais cuidado ou pelo menos investiria em soft skills para compensar o débito acadêmico. Quando você fizer um teste possivelmente alguém que faz ciências da computação vai disputar a vaga com você e ela já conhece isso por padrão.

Isso é um logaritmo:

log2(8) = 3

Leia-se, log na base 2 de 8 é igual a 3 e porque é igual a 3?

Porque a pergunta desse logaritmo é “qual numero eu uso na exponenciação para 2 que resulta em 8?”.

Então será 3 porque 2³ (dois ao cubo) é 2 * 2 * 2 = 8 fim do mistério.

E porque logaritmos são o inverso da exponenciação? Pois através do logaritmo de N temos o numero de operações.

O numero de operações é:

log 2(n) = x

Onde x é o numero de operações realizadas durante a execução do algoritmo.

Infelizmente nem tudo são flores e nem todo logaritmo é na base de 2 mas esse calculo não é a parte mais importante, repare que até aqui falamos sobre as complexidades e elas tem exemplos matemáticos como a exponenciação mas não fazemos contas realmente pra chegar na notação do algoritmo.

Então, para uma lista de 8 números, você teria que verificar 3 números no máximo. Para uma lista de 1.024 elementos, log 1.024 = 10, porque 2 elevado a 10 == 1.024. Então, para uma lista de 1.024 números, você tem que verificar 10 números no máximo.

Um exemplo de algoritmo com complexidade O(log n) é uma busca binária em uma lista já ordenada.



package main

import "fmt"

func main() {
    arr := []int{2, 3, 4, 10, 40}
    item := 9
    busca := buscaBinaria(arr, 0, len(arr), item)
    fmt.Println(busca)
}

func buscaBinaria(arr []int, esquerda, direita, item int) bool {
    for esquerda <= direita {
        meio := esquerda + (direita-esquerda)/2

        if arr[meio] == item {
            return true
        }

        if arr[meio] < item {
            esquerda = meio + 1
        } else {
            direita = meio - 1
        }
    }
    return false
}

Esse tipo de algoritmo é bem simples você parte o input ao meio e ai compara pra verificar se o item a ser buscado é menor ou maior que o item no meio do array. Quando isso acontece você joga fora metade da lista ficando com uma parte menor e esse processo é repetido até que se encontre o item da busca diminuindo cada vez mais o processamento, por isso ele é o inverso do exponencial você diminui o N toda vez que um processamento é feito.

Nesse exemplo do gráfico da pra verificar que o numero varia muito porém o tempo é irrelevante em relação a outras complexidades ali em baixo o input é de 1pb e o tempo de 3 milésimos. O gŕafico mostra como N aumenta e logo em seguida se torna quase uma constante, isso acontece porque mesmo que N duplique o algoritmo sempre vai estar fatiando N pela metade várias vezes até encontrar o resultado.

Como um rapaz disse no tweet que em que perguntei sobre log n esses dias “como você explicaria log n para um Júnior/Sandy”, ele disse:

Vou deixar aqui o link do Tweet pra quem quiser ver mais sobre Log N pois tiveram diversos pontos de vista sobre e podem ajudar mais pessoas.

Esse exemplo da busca binária só funciona quando se tem uma lista ordenada caso contrário o algoritmo não poderia garantir que o elemento procurado está de fato em uma metade ou outra da lista, sendo necessária outra abordagem.