DEV Community

Cover image for BigO
Wagner Abrantes
Wagner Abrantes

Posted on

BigO

Analise da complexidade de algoritmos

Como tornar seu algoritmo mais escalável que as tretas do Twitter?

Quando se começa a programar tem um momento durante o aprendizado em que você tem um “click” você começa a pensar nos problemas do ponto de vista de um programador. Não tem mais volta, você está fadado ao resto da vida a olhar para um interruptor e pensar:

    if interruptor == up {
        turnLightOn()
    } else {
        turnLightOff()
    }
Enter fullscreen mode Exit fullscreen mode

Parece que o cérebro funciona com lógica boleana, só que não, você levou muito tempo para que em determinado momento a sua cabeça se voltasse para as coisas dessa forma, isso é a construção de muito trabalho, ao mesmo tempo parece que foi sim um “click”, isso porque não percebemos a nós mesmos com muita clareza.

Um dos “clicks” que ainda podem acontecer ou já aconteceu com você, é quando temos um determinado problema e para resolvê-lo deixamos de pensar assim: “Como posso resolver isso?

Para pensar assim: “Já sei como resolver, mas essa solução é suficiente?” ou “ela é escalável ou legível?”.

Até conseguimos resolver problemas, porém quando somos iniciantes e todo desafio proposto parece complicado nossa única preocupação é apenas resolver da forma que for possível. A mudança aqui é quando já temos bagagem em resolver problemas, só que agora levamos menos tempo e temos o privilégio de pensar em uma implementação diferente.

Acho aceitável uma solução não escalável em um cenário onde se é iniciante, não cobraria isso de alguém que é um estagiário por exemplo, nem daria acesso a ele pontos do sistema que possam ser críticos.

Não quero ser o cara que fala “se você não sabe Estrutura de Dados e Algoritmos você é mal programador”, mas se você quer ter um segundo “click” e começar a ver a programação sob mais uma perspectiva recomendo muito que estude sobre.

COMPLEXIDADE DE ALGORITMOS

A complexidade de um algoritmo é analisada em termos de tempo e espaço. Normalmente, o algoritmo terá um desempenho diferente com base no processador, disco, memória e outros parâmetros de hardware. A complexidade é usada para medir a velocidade de um algoritmo. Sendo o Algoritmo um agrupamento de etapas para se executar uma tarefa. O tempo que leva para um algoritmo ser concluído é baseado no número de passos.

Digamos que um algoritmo percorre um array de dez posições somando o índice das posições a 200.

A complexidade seria de 10 X T, sendo que T representa o tempo necessário para atualizar todos os elementos do array com a operação de soma. Como cada computador pode ser muito diferente um do outro isso varia de acordo com o hardware, a linguagem utilizada e o sistema operacional.

package main

import "fmt"

func main() {
        var arr [10]int
        for indice := 0; indice < len(arr); indice++{
            arr[indice] = indice + 200
            fmt.Printf("indice[%d] = %d\n", indice, arr[indice])
        }
}
Enter fullscreen mode Exit fullscreen mode

Output:

indice[0] = 200
indice[1] = 201
indice[2] = 202
indice[3] = 203
indice[4] = 204
indice[5] = 205
indice[6] = 206
indice[7] = 207
indice[8] = 208
indice[9] = 209
Enter fullscreen mode Exit fullscreen mode

Temos 10 operações acontecendo, aparentemente muito simples.

Com uma Notação é possível calcular a complexidade de um algoritmo sem precisar levar em consideração parâmetros de hardware.

BIG O NOTATION

A Big O Notation é uma notação especial que indica a complexidade de um algoritmo. Na realidade existem várias notações: big e small O, big e small omega e theta. A notação do O é sobre “limite por cima”, a omega sobre “limite por baixo” e a theta é a combinação de ambos. Os ‘small’ representam afirmações mais rígidas sobre a complexidade do que os ‘big’. Geralmente a big O é mais utilizada porque o interesse é verificar o máximo de recursos que o algoritmo vai utilizar, sem tanta rigidez, e então tentar reduzir isso, quando possível.

A função de tempo T(n) representa a complexidade do algoritmo onde T(n) = O(n) afirmando que um algoritmo tem uma complexidade linear de tempo. Pois o TEMPO é completamente relacionado a N o tamanho de input do algoritmo (e às vezes também outros aspectos).

Geralmente a maioria do material relacionado a Big O é formal demais, talvez isso afaste um pouco as pessoas mas com um pouquinho de dedicação a gente consegue enxergar os padrões.

Em Big O Notation as complexidades de tempo linear, logarítmica, cúbica e quadrática são representações de complexidades diferentes de relação entre T e N em um algoritmo. A Big O Notation também é usada para, determinar quanto espaço é consumido pelo algoritmo.

Então você pode visualizar de forma gráfica como funciona o crescimento de tempo e de tamanho do input e como eles se relacionam. No final é sobre isso, a relação entre um ou mais aspectos da entrada e o tempo de execução do algoritmo. Importante: nem sempre o desempenho do algoritmo é afetado apenas pelo tamanho da entrada. O algoritmo de ordenação counting sort, por exemplo, é afetado também pelo maior número na lista.

Vou falar sobre as principais funções de complexidade, e pretendo dar maior enfase na complexidade de tempo, mais tarde assuntos como recursão vão aparecer então vou diluindo isso durante o processo. Você pode estar se perguntando “ok mas como eu calculo isso?” como eu descubro a complexidade do meu algoritmo?

Discussion (0)