Análise de Algoritmos c/ Python
Parte 2
Big-O Notation (Notação Big-O)
Big-O notation is a way to express the efficiency of an algorithm. If you’re going to be working with code, it is extremely important that you understand Big-O. It is, quite literally, the language we use to express efficiency. Gayle Laakmann McDowell on Quora.
Big-O é uma expressão de como o tempo de execução de um algoritmo é escalado com um dado de entrada. Supondo que um dado de entrada é “n”, se esse dado de entrada ficar cada vez maior, quanto tempo a mais ele irá gastar? Apenas um pouquinho? Muito mais tempo? Aí que entra a notação Big-O para analisar o tempo gasto a mais, e medir a eficiência do algoritmo.
Para relembrar o algoritmo do post Análise de Algoritmos c/ Python — Parte 1, postarei aqui uma foto:
Uma boa base para comparação dos algoritmos é contar o número de atribuição. No caso da função sumOfN2(), seria contar o número de atribuição da variável theSum.
Let’s count…
Na primeira parte temos a atribuição theSum = 0, ou seja, uma atribuição. Dentro do for loop temos mais uma atribuição (theSum = theSum + i). Mas nesse caso, por conta do loop, essa atribuição ocorre n vezes, já o loop corre de 1 até n (range(1, n + 1)). Assim temos: 1 + n, como o número de atribuições de theSum dentro da função. Podemos simbolizar esse número como uma função, chamada T, onde T(n) = 1 + n.
“T(n) é o tempo que necessita para resolver um problema de tamanho n, com 1 + n passos.”
Quando o n começa a ficar maior, a constante 1 fica cada vez menos significante, tanto que podemos aproximar T(n) = n e o tempo de execução será O(n).
Obs. É necessário dizer que a constante 1 continua sendo significante, porém menos quando o n representa um número muito maior.
Vamos para um outro exemplo: suponha que um algoritmo tenha exatamente esse número de passos T(n)=5n²+27n+1005. Quando o n é pequeno, por exemplo 1 ou 2, a constante 1005 é a parte dominante da função. Porém, quando n vai crescendo, a parte da função que se torna mais significante é o n². E quando o n é extremamente grande, as outras duas partes (27n + 1005) são menos significativas, então podemos “ignorá-los” e focar no 5n². Outra coisa é que o coeficiente 5 também se torna insignificante quando o n é muito grande. Então podemos aproximar a função para T(n) = n², ou simplesmente O(n²).
Algumas vezes, a performance de um algoritmo não depende simplesmente do tamanho do problema a ser resolvido. Para especificamente esses algoritmos, nós caracterizamos a sua performance em termos de performance de melhor caso (best case), pior caso (worse case) ou caso médio (average case).
Nessa tabela é mostrado a relação de cada função com o seu devido nome:
A tabela mostra, também, que ao descer cada linha da tabela, o tempo de execução, da determinada função, aumenta. Ou seja, a função Constante é mais rápida que a função log n. E assim por diante..
E esta imagem é a representação gráfica da tabela anterior:
Esse gráfico representa a relação entre as funções já denominadas. Na abscissa (Eixo Horizontal) significa o n da função, e na ordenada (Eixo Vertical) significa o tempo decorrido para executar tal n.
Com essa descrição, podemos perceber que, ao executar um n aleatório, a função logarítmica é mais rápida que a linear e constante é a mais rápido dentre todas, ficando dessa forma:
1 > log n > n > n log n > n² > n³ > 2^n
Vamos entender com um exemplo prático a performance de um algoritmo. Vejamos esse seguinte:
Obs: Esse algoritmo faz absolutamente nada, porém será um bom exemplo para entender como funciona a performance baseada no Big-O.
- Analisando:
Para montar a função desejada comecemos pelas 3 constantes no início. Há 3 atribuições, sem nenhuma iteração. Então o primeiro termo é a constante 3.
O segundo termo se refere ao for aninhado. Será n² vezes, mas como há 3 atribuições, fica 3n². Portanto, o segundo termo é 3n².
O terceiro termo é composto da iteração for. É um for simples, sem aninhamento, ou seja, são n vezes, e com duas atribuições fica 2n.
E finalmente, o último termo refere-se a atribuição, o que dá a constante 1 (apenas uma atribuição).
Com essa análise do algoritmo, podemos chegar na função desejada:
Como vimos antes, apenas olhando os expoentes, podemos identificar que o n² será o fator dominante, então essa função é O(n²).
O comportamento dessa função T(n) é ilustrado pelo gráfico:
Já que essa função é O(n²), então seguirá a função quadrática. Tem velocidade maior que a função cúbica, e menor que a função quadrática, já que possui elementos a mais (constante 4 e fator 2n —> 3n² + 2n + 4).
Após essa parte 2, podemos entender melhor como funciona a performance de um algoritmo baseado na notação Big-O (Big-O Notation). Na próxima parte, chegaremos na análise das estruturas de dado do Python relacionado à performance dos algoritmos.
See ya..
