Sou desenvolvedor Front-end e estou aprofundando meus estudos na base da programação. Dessa maneira, comecei estudar algoritmos e estrutura de dados e vou postar os resumos que venho fazendo sobre alguns tópicos desses temas.
Assim, vou apresentar um resumo geral sobre Big-O. Aqui você irá ver sobre:
- Algoritmos
- Estruturas de Dados
- Conceito de Big-O
- A complexidade das funções por meio do Big-O
- Como analisar o algoritmo por meio do Big-O
- Como comparar dois algoritmos utilizando Big-O
Algoritmos
O algoritmo é o passo a passo para executarmos uma tarefa,já a lógica, é o que utilizamos para organizar esse passo a passo e a estrutura de dados é a forma que organizamos e dispomos nossos dados. Para facilitar o entendimento, vamos supor que iremos seguir um trajeto de um ponto A ao ponto B. Para chegarmos, nós precisamos de uma trajetória, montamos, então, o algoritmo para sair do ponto A ao ponto B. Para isso, é necessário utilizar a lógica, a fim de montar este trajeto e obter sucesso. Além disso, podemos estruturar esse caminho de várias formas.
Duas pessoas podem sair do mesmo ponto e chegar ao mesmo local, utilizando caminhos diferentes. Um caminho pode ser mais eficiente do que o outro, ou seja, uma pessoa pode ter melhor performance do que a outra ao escolher esse caminho. Podemos mensurar esse rolê por meio do tempo gasto ou da distância percorrida. São bons parâmetros não é mesmo!?
Big-O
Bom, o Big-O serve para mensurar de forma objetiva a performance de diferentes algoritmos. Dessa maneira, podemos dizer qual caminho é mais performático. Entretanto, ele não vai levar em consideração a linguagem que será utilizada, o poder de processamento do hardware, ou qual será o sistema operacional. Voltando a história, é como se considerarmos que os dois tiveram a mesma velocidade média e também as mesmas condições. Como se falasse assim: nas mesmas condições, X é mais eficiente que Y, considerando somente o caminho que cada um tomou. Assim, quem estruturou o melhor caminho e montou o melhor passo a passo, será o mais eficiente.
No python, há uma biblioteca chamada timeit, uma das funcionalidades dela é calcular o tempo de execução de um algoritmo. Vou demonstrar uma função básica que tem objetivo de receber um número(n) e esse número será somado de 0 até ele mesmo. Exemplo: Se ‘n’ for 3, a função irá fazer 0+0, 0+1, 1+2, 3+3, sendo o resultado 6. O primeiro passo a passo (algoritmo), coloquei um laço de repetição.
Após isso, utilizei a biblioteca para contar o tempo. A primeira retornou em 560 nanosegundos, ou seja, 560 x 10 elevado -9. Na segunda opção, para chegar ao mesmo resultado, eu montei uma expressão. A segunda executou em 106 ns, ou seja, bem mais rápida que a primeira. Saímos de um mesmo ponto e chegamos a um mesmo ponto, entretanto utilizando algoritmos diferentes, sendo um mais performático que o outro.
Um dos motivos da discrepância de tempo é o número de passos de uma operação em relação a outra. Na primeira, precisamos incrementar e calcular diversas vezes, já na segunda o número de passos é bem menor. Enquanto na soma1 precisaremos executar 11(1 para criar a variável soma e os outros 10 nas operações do laço) passos, na soma2, executaremos somente 3 passos, independente do valor de n, os passos são fixos. Lembrando que a primeira função executa 11 passos, pois é o exemplo com n=10, se n=1000 ele irá executar 1001 passos.
Mas atenção, essa ainda não é a notação Big-O. Primeiramente, a notação Big-O é representada assim O(n), onde (n) é o número de passos.
Na primeira função, o Big-O é O(n), enquanto o da segunda é O(3). Nisso nós conseguimos verificar o quanto a complexidade do algoritmo aumenta de acordo com as entradas.
Big-O é uma notação do campo da matemática que avalia o comportamento limite de uma função em relação ao valor dos argumentos utilizados.
Irei mostrar mais um exemplo. Vou fazer uma lista em python com 1000 números. A primeira forma utilizei um laço de repetição, já a segunda utilizei uma função (range) do python que insere o número n na lista de forma muito mais otimizada. Perceba a diferença de tempo. Enquanto uma é 10 elevado a -6, a segunda é elevada a -9, ou seja, a segunda é muito mais rápida.
Em notação Big-O, a primeira será O(n), ou seja, a complexidade da função varia de acordo com a entrada e a segunda não conseguimos definir exatamente a quantidade de passos, pois teríamos que avaliar como foi feita essa funcionalidade, entretanto, como em relação ao tempo ela executa mais rapidamente, ela tem um número de passos muito menor que a primeira.
Complexidade Big-O
- Constante O(1)
- Linear O(n)
- Logarítmico O(n log n)
- Quadrático O(n²)
- Exponencial O(2^n)
- Fatorial O(n!)
- Polinomial 2^{O(log n)}
Gráfico complexidade Big-O:
Podemos notar que quanto mais complexo, mais vermelho fica e, com isso, pior será o seu algoritmo. Sabendo em qual os algoritmos encaixam, fica mais fácil de comparar. Exemplo, na imagem 1 e função soma1, encaixamos na notação O(n), o que significa que ela é Linear, enquanto a segunda função (soma2), é constante. Portanto, a soma2 é melhor segundo a notação Big-O. Da mesma forma notamos na segunda imagem.
As recomendações de vídeos irão clarear muito bem esses conceitos de Big-O.
Bora para mais exemplos!?
Constant O(1):
Neste exemplo, eu coloquei uma lista com alguns números e criei uma função que retorna o primeiro elemento:
Repare que como eu retorno o primeiro elemento, a notação big-o será O(1), ou seja, será constante, pois sempre terá um só passo.
Linear O(n):
Quanto maior o n, maior será o número de passos.
Quadratic O(n²)
Quando há um laço de repetição dentro de outro laço de repetição, é um big-o quadratic (usado para percorrer matrizes). Se houvesse outro for aí dentro, seria cúbica.
Finalizando, um exemplo de uma combinação com mais de um tipo:
Caso tenha alguma sugestão sobre o tema, mande mensagem. Será muito bom evoluir com sua ajuda! Obrigado por chegar até aqui e espero ter ajudado!
Mais sobre esse tema:
Big-O Javascript
Top comments (0)