Os Fundamentos da Notação Big-O

Como utilizar a notação Big-O para medir o desempenho e a escalabilidade do seu algoritmo

Foto de Nadine Shaabana no Unsplash

Na era em que os dados crescem cada vez mais, não é mais suficiente criar um algoritmo que “simplesmente funcione” para resolver o problema. Não importa qual seja sua profissão, seja desenvolvedor de software, cientista de dados ou engenheiro de aprendizado de máquina, a capacidade de criar um algoritmo eficiente e escalável é uma habilidade altamente desejável.

Para criar um algoritmo eficiente, na maioria das vezes precisamos pensar fora da caixa para ter uma idéia de como otimizar o desempenho do código. E quando tentamos otimizar o código, às vezes não sabemos como medir a eficiência do nosso algoritmo — se ele foi melhorado ou não.

Neste post, vamos falar sobre como você pode medir o desempenho do seu algoritmo utilizando a notação Big-O.

Maneira correta de medir o desempenho de um algoritmo

Antes de tudo, vamos pensar por um momento: como sabemos que nosso algoritmo é bom ou eficiente? como medimos o desempenho do nosso algoritmo? Provavelmente, a maneira mais fácil de medir o desempenho do algoritmo é medindo o tempo necessário para calcular a solução.

No entanto, medir a duração do tempo não é uma ótima maneira de avaliar o desempenho do seu algoritmo porque:

• O computador que estamos usando terá um enorme impacto na rapidez com que o algoritmo é executado. Se você estiver usando um hardware antigo, é esperado que o código seja executado mais lentamente do que se estivesse usando um hardware mais novo.
• Se você executar o algoritmo enquanto outros programas se encontram abertos e ativos em seu computador, o tempo necessário para que seu algoritmo resolva a solução será mais lento do que se seu computador dedicasse todos os seus recursos para executar o algoritmo.
• O compilador e as bibliotecas que usamos em nosso algoritmo também afetam sua duração de tempo de execução.

Portanto, deve haver uma maneira melhor de medir o desempenho do algoritmo.

Ao invés de focar na duração do tempo para executar seu algoritmo, precisamos nos concentrar mais na escalabilidade ou complexidade do tempo de execução do nosso algoritmo: como o desempenho do nosso algoritmo muda à medida que o tamanho da entrada aumenta?

Para medir a complexidade do tempo de execução do nosso algoritmo, insira o conceito por trás da notação Big-O.

A notação Big-O

A notação Big-O é o termo que você costuma ouvir em Ciência da Computação quando fala sobre eficiência de algoritmo. Mas, o que significa a notação Big-O?

Em termos simples, a notação Big-O descreve quão bom é o desempenho do seu algoritmo à medida que os dados de entrada crescem.

Com a notação Big-O, podemos medir a escalabilidade do nosso algoritmo: nosso algoritmo ainda terá um bom desempenho à medida que a entrada cresce?

Neste post vamos falar sobre quatro das notações Big-O mais comuns:

• O(1)
• O(n)
• O(n²)
• O(log n)

Esses Os significam Order Of , então O(n) significa Order Of n , onde n é o tamanho dos dados de entrada.

Vamos analisar essas notações uma por uma.

O(1) — Complexidade de tempo de execução constante

A notação O(1) significa que seu algoritmo tem uma complexidade de tempo de execução constante porque leva o mesmo número de operações, independentemente do tamanho dos dados de entrada.

Para torná-lo mais intuitivo, vamos dar uma olhada no trecho de código abaixo.

def array_elements(array):
  print(array[0])

O trecho de código acima é o exemplo simples de um algoritmo com notação O(1) . A função recebe um array e exibe o primeiro elemento do array. Não importa quantos elementos existam no array, esta função sempre será executada em um tempo de execução constante porque seu trabalho é apenas exibir o primeiro elemento do array.

Vamos dar uma olhada em outro algoritmo que tem complexidade de tempo O(1) .

def array_elements(array):
  third_index = array[2]
  return third_index

No trecho de código acima, a função recebe um array e seu trabalho é atribuir o terceiro elemento do array a uma variável chamada third_index. Novamente, não importa quão grande seja o tamanho da matriz de entrada, a função sempre será executada em um tempo de execução constante porque seu único trabalho é atribuir o valor do terceiro elemento da matriz a uma variável.

Agora, se plotarmos a complexidade de tempo do algoritmo com notação O(1) com o tamanho dos dados de entrada, obteremos o seguinte gráfico.

Como você pode ver, a complexidade do tempo de execução do algoritmo permanece constante à medida que os dados de entrada crescem cada vez mais.

O(n) — Complexidade de tempo de execução linear

A notação O(n) significa que a complexidade do tempo de execução do seu algoritmo tem uma relação linear com o tamanho dos dados de entrada. Se o tamanho dos dados de entrada for aumentado em 2, a complexidade do tempo de execução do seu algoritmo também será aumentada em 2.

Vamos dar uma olhada no trecho de código abaixo para torná-lo mais intuitivo.

def array_element(array):
  for i in range (len(array)):
  print(array[i])

Ter um loop iterando sobre os elementos de um array e imprimindo o valor de cada um de seus elementos é o exemplo perfeito de um algoritmo que possui notação O(n) .

No trecho de código acima, o custo do nosso algoritmo muda em relação ao tamanho do array de entrada. Se a matriz de entrada tiver apenas 2 elementos, nosso algoritmo levará apenas 2 operações para ser executado. Se a matriz tiver 100 elementos, o algoritmo também levará 100 operações para ser executado. Em outras palavras, o custo do nosso algoritmo aumenta linearmente com o tamanho do array de entrada.

Agora, se plotarmos a complexidade do tempo de execução com o tamanho dos dados de entrada, obteremos o seguinte gráfico.

Como você pode ver, temos uma relação linear entre a complexidade do tempo de execução e o tamanho dos dados de entrada. Quanto mais elementos houver na matriz de entrada, mais operações serão necessárias para que nosso algoritmo seja executado.

O(n²) — Complexidade de tempo de execução quadrática

A notação O(n²) significa que a complexidade do tempo de execução do seu algoritmo é proporcional ao quadrado do tamanho da entrada. Digamos que o tamanho de entrada do seu array seja 3, então a complexidade do tempo de execução do seu algoritmo será aumentada em 9.

Vamos dar uma olhada no trecho de código abaixo como exemplo de algoritmo com complexidade O(n²) .

def array_element(array):
  sum_number = 0
  for i in range (len(array)):
    for j in range (len(array)):
      sum_number += array[i]+array[j]
  return sum_number

Loops aninhados são o exemplo perfeito de um algoritmo com notação O(n²) . Isso ocorre porque o loop está iterando sobre cada elemento de uma matriz duas vezes. O loop interno tem a complexidade de O(n) , e o loop externo também tem a complexidade de O(n) . Agora, se combinarmos a complexidade entre o loop interno e o loop externo, obtemos a complexidade de O(n²) .

Digamos que o tamanho do nosso array de entrada seja 3. Para loop externo, são necessárias no total 3 operações para iterar sobre cada elemento de um array. Para cada uma dessas 3 operações, também são necessárias 3 operações para fazer o loop interno para iterar sobre cada elemento. Isso leva a 9 operações no total.

Se traçarmos o gráfico, você obterá a seguinte visualização para um algoritmo com complexidade O(n²) .

Como podemos ver, o custo do nosso algoritmo será muito mais caro à medida que o tamanho dos nossos dados de entrada for aumentado.

O(log n) — Complexidade logarítmica de tempo de execução

A próxima complexidade de tempo de execução que devemos conhecer é O(log n) . Essa notação significa que a complexidade do tempo de execução do seu algoritmo será aumentada em um quando o tamanho dos dados de entrada forem duplicados.

Vamos dar uma olhada no trecho de código abaixo como exemplo.

def binary_search(array, value):
    first_val = 0
    last_val = len(array)-1
    bool_stat = False
    while (first_val <= last_val and bool_stat == False):
        mid_val = (first_val + last_val) // 2
        if array[mid_val] == value:
           bool_stat = True
           return bool_stat
        elif value > array[mid_val]:
           first_val = mid_val + 1 
        else:
           last_val = mid_val - 1
    return bool_stat
array = [1,2,3,4,5,6,7,8,9]
value = 7
is_found = binary_search(array, value)

O trecho de código acima é o algoritmo de busca binária que tem uma complexidade de tempo de execução de O(log n) . Em vez de iterar sobre cada elemento de uma matriz com loop for , a pesquisa binária sempre dividirá recursivamente o tamanho dos dados de entrada pela metade para encontrar o valor desejado.

Conforme mostrado no código acima, temos um array com tamanho de entrada 9. Supondo que os dados estejam perfeitamente ordenados, nosso objetivo é descobrir se o valor de 7 existe neste array. A busca binária primeiro dividirá o array de entrada ao meio e verificará o valor no meio do nosso array.

Como o valor no meio do nosso array é 5, esse valor será então verificado com o valor que estamos procurando, que neste caso é 7. Como 5 é menor que 7, então o algoritmo usará os valores em do lado direito da matriz, que são de 6 a 9.

Agora o tamanho de entrada do nosso array é 4 em vez de 10. O novo array então será dividido novamente pela metade, o que nos deixa com um array com um valor de 6 e 7 e um array com um valor de 8 e 9.

Como o valor de 7 está na matriz de 6 e 7, o algoritmo usará essa parte de uma matriz e ignorará a matriz com o valor de 8 e 9.

Até que finalmente encontramos o valor que queremos, que é 7.

Se desenharmos o gráfico do algoritmo com a complexidade de tempo de execução de O(log n) , obteremos a seguinte visualização.

Como você pode ver, o algoritmo que tem notação O(log n) é mais escalável que O(n) e O(n²) à medida que o tamanho da entrada cresce cada vez mais.

Em nosso exemplo acima, se usarmos o loop for , que tem uma notação linear O(n) , nosso algoritmo precisará de 7 operações antes de encontrar uma solução (já que estamos procurando o valor 7). Enquanto isso, com o algoritmo de busca binária, que tem notação O(log n) , são necessárias apenas 4 operações para resolver o problema.

Comparações de complexidade entre diferentes notações Big-O

Vamos recapitular um pouco sobre as diferentes notações Big-O que aprendemos até agora em termos de escalabilidade. Abaixo está o gráfico dessas notações Big-O.

Como você pode ver, o algoritmo com notação O(1) tem a melhor escalabilidade à medida que o tamanho da entrada cresce cada vez mais, enquanto o algoritmo com notação O(n²) tem a pior escalabilidade entre todos.

Para resumir, abaixo está a ordem de escalabilidade da notação Big-O iniciada do melhor para o pior:

**O(1) < O(log n) < O(n) < O(n^2)**

Determinando a notação Big-O de um código

Agora que conhecemos diferentes tipos de notação Big-O, vamos tentar descobrir a complexidade de tempo de execução de um código. Quando tentamos analisar a complexidade de tempo de execução de um código, sempre temos que enfrentar dois cenários diferentes: o melhor cenário e o pior cenário.

Melhor cenário e pior cenário

Para facilitar o entendimento da diferença entre o melhor cenário e o pior cenário, vamos dar uma olhada no trecho de código abaixo:

def linear_search(array, value):
    for i in range (len(array)):
        if array[i] == value:
           return True
    return False
def binary_search(array, value):
    first_val = 0
    last_val = len(array)-1
    bool_stat = False
    while (first_val <= last_val and bool_stat == False):
        mid_val = (first_val + last_val) // 2
        if array[mid_val] == value:
           bool_stat = True
           return bool_stat
        elif value > array[mid_val]:
           first_val = mid_val + 1 
        else:
           last_val = mid_val - 1
    return bool_stat
array = [1,2,3,4,5,6,7,8,9]
value = 7

No trecho de código acima, temos um algoritmo para pesquisa linear (iterando os elementos de cada array com loop for ) e um para pesquisa binária (dividindo recursivamente o array). Digamos que temos um array perfeitamente ordenado com 9 elementos como você pode ver acima.

• O melhor caso para pesquisa linear seria se quisermos pesquisar o valor de 1, que é o primeiro elemento da matriz. Neste caso, temos complexidade O(1) .
• O pior caso para pesquisa linear seria se quisermos pesquisar o valor de 9, que é o último elemento do array, ou se quisermos pesquisar um valor que não esteja incluído no array. Isso ocorre porque o algoritmo precisa percorrer cada elemento da matriz. Neste caso, temos complexidade O(n) .
• O melhor caso para pesquisa binária seria se quiséssemos pesquisar o valor de 5, que é o valor no elemento do meio da matriz. Neste caso, temos complexidade O(1) .
• O pior caso para a busca binária seria se quiséssemos buscar o valor de 1 ou 10, que são o primeiro e o último elemento do array, ou o valor que não está incluído no array. Isso ocorre porque com a busca binária, o algoritmo precisa dividir os dados ao meio recursivamente até atingir o primeiro e o último elemento. Neste caso, temos a complexidade de O(log n).

Estimando a notação Big-O de um código

Quando se trata de determinar a notação Big-O de um código, precisamos sempre olhar para a perspectiva do pior cenário. Agora com esse conceito em mente, vamos tentar estimar a notação Big-O de um código.

Vamos dar uma olhada no trecho de código abaixo e vamos verificar sua complexidade.

def max_value(array):
    value = 0  # O(1) complexity
    for i in range (len(array)): # O(n) complexity
        for j in range (len(array)-10): # O(10) complexity
            for k in range (len(array)//2): # O(n/2) complexity
                value += array[i] + array[j] + array[k] # O(1) complexity
    return value # O(1) complexity

Ao estimar a notação Big-O de um código, precisamos sempre observar primeiro a operação no loop mais interno. Abaixo segue o passo a passo de como devemos investigar a complexidade do Big-O do código acima:

1. A partir da operação no loop mais interno, que é value += array[i] + array[j] + array[k]. Esta operação tem uma complexidade O(1) constante.
2. Em seguida, olhamos para o loop mais interno, que é for k in range (len(array)/2). Esse loop sempre iterará mais da metade do tamanho do nosso array, portanto, tem complexidade O(n/2) .
3. Em seguida, subimos um nível, que é o loop for j in range (len(array)-10). Embora este seja um loop for , mas tem uma complexidade de tempo de execução constante. Isso ocorre porque não importa quão grande seja o tamanho da matriz de entrada, esse loop sempre iterará apenas nos últimos 10 elementos. Portanto, tem uma complexidade O(10) constante.
4. Em seguida, passamos para o loop externo, que é for i in range (len(array)). Este loop for sempre iterará sobre o tamanho da matriz de entrada. Portanto, esse loop tem complexidade O(n) .
5. Finalmente, passamos para as operações fora do loop, que são value = 0e return value. Essas duas operações sempre serão executadas em um tempo de execução constante, portanto, ambas têm complexidade O(1) .

Agora que analisamos a notação Big-O de todos os loops e operações, a seguir vamos analisar a notação Big-O de todo o código. Para fazer isso, também precisamos sempre começar do loop mais interno.

1. O loop mais interno tem complexidade O(n/2) e a operação neste loop tem complexidade O(1) . Isso significa que esse loop mais interno tem complexidade.(n/2)*(1) = **O(n/2)**
2. Em seguida, o segundo loop interno tem complexidade O(10) . O loop interno deste loop, como computamos no ponto nº 1, tem O(n/2) . Isso significa que o segundo loop interno tem complexidade.10*(n/2) = **O(5n)**
3. Finalmente, o loop externo tem complexidade O(n) . O loop interno deste loop externo tem uma complexidade total de O(5n) , conforme computamos no ponto no.2. Então, no total, eles têm complexidade.n*5n = **O(5n^2)**
4. Se combinarmos a complexidade do loop e as duas operações fora do loop, obtemos . Como você pode ver, o código acima no total tem complexidade O(2+5n²) .1+1+5n^2 = **O(2+5n^2)**

Quando estamos estimando a notação Big-O de um código, podemos simplificá-la eliminando todas as constantes. Então, em vez de O(2+5n²) , podemos descartar todas as constantes e ficar com O(n²) . Portanto, o código acima tem complexidade O(n²) .

E é isso por enquanto!

Espero que agora você saiba como medir e estimar o desempenho de um algoritmo observando sua notação Big-O. Projetar um algoritmo escalável é muito benéfico para otimizar o código à medida que os dados de entrada crescem cada vez mais a cada dia.

Créditos

• The Fundamentals of the Big-O Notation, escrito originalmente por Ruben Winastwan.