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:
- 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. - 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) . - 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. - 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) . - Finalmente, passamos para as operações fora do loop, que são
value = 0ereturn 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.
- 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)** - 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)** - 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)** - 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.
Top comments (1)
Excelente!