Big O Notation é um conceito matemático usado para descrever o desempenho ou a complexidade de um algoritmo em termos de tempo e espaço à medida que o tamanho da entrada aumenta. Isso nos ajuda a entender como o tempo de execução de um algoritmo aumenta com entradas maiores, permitindo uma comparação mais padronizada de diferentes algoritmos.

Por que usar a notação Big O?

Ao comparar algoritmos, confiar apenas no tempo de execução pode ser enganoso. Por exemplo, um algoritmo pode processar um enorme conjunto de dados em uma hora, enquanto outro leva quatro horas. No entanto, o tempo de execução pode variar de acordo com a máquina e outros processos em execução. Em vez disso, usamos a notação Big O para focar no número de operações realizadas, o que fornece uma medida de eficiência mais consistente.

Exemplo: somando números

Vamos explorar duas maneiras de calcular a soma de todos os números de 1 a n:

Opção 1: usando um loop

function addUpTo(n) {
    let total = 0;
    for (let i = 1; i 




  
  
  Opção 2: usando uma fórmula




function addUpTo(n) {
    return n * (n   1) / 2;
}





  
  
  Analisando a Complexidade


Na Opção 1, se n for 100, o loop será executado 100 vezes. Em contraste, a Opção 2 sempre executa um número fixo de operações (multiplicação, adição e divisão). Por isso:

• Opção 1 é O(n): A complexidade do tempo cresce linearmente com n.
• Opção 2 é O(1): A complexidade do tempo permanece constante, independentemente do tamanho da entrada.

Isenção de responsabilidade

Embora a Opção 2 envolva três operações (multiplicação, adição, divisão), nos concentramos na tendência geral na análise Big O. Assim, em vez de expressá-lo como O(3n), simplificamos para O(n). Da mesma forma, O(n 10) simplifica para O(n) e O(n^2 5n 8) simplifica para O(n^2). Na notação Big O, consideramos o pior cenário, onde o termo de ordem mais alta tem o maior impacto no desempenho.

Existem outras formas de notação além das complexidades comuns listadas acima, como a complexidade de tempo logarítmica expressa como O(log n).

O que é notação Big O?

Big O Notation nos permite formalizar o crescimento do tempo de execução de um algoritmo com base no tamanho da entrada. Em vez de focar em contagens de operações específicas, categorizamos algoritmos em classes mais amplas, incluindo:

• Tempo constante: O(1) - O desempenho do algoritmo não muda com o tamanho da entrada.
• Tempo Linear: O(n) - O desempenho cresce linearmente com o tamanho da entrada.
• Tempo quadrático: O(n^2) - O desempenho cresce quadraticamente à medida que o tamanho da entrada aumenta.

Exemplo de O (n ^ 2)

Considere a seguinte função, que imprime todos os pares de números de 0 a n:

function printAllPairs(n) {
    for (var i = 0; i 



Nesse caso, a função possui dois loops aninhados, portanto, quando nnn aumenta, o número de operações aumenta quadraticamente. Para n= 2, existem 4 operações, e para n=3, existem 9 operações, levando a O(n^2).


  
  
  Outro exemplo: contagem crescente e decrescente




function countUpAndDown(n) {
    console.log("Going up!");
    for (var i = 0; i = 0; j--) {
        console.log(j);
    }
    console.log("Back down. Bye!");
}





À primeira vista, pode-se pensar que é O(n^2) porque contém dois loops. No entanto, ambos os loops são executados de forma independente e escalam linearmente com n. Assim, a complexidade geral do tempo é O(n).


  
  
  Simplificando a análise


A análise de cada aspecto da complexidade do código pode ser complexa, mas algumas regras gerais podem simplificar as coisas:

• As operações aritméticas são consideradas tempo constante.
• As atribuições de variáveis ​​são de tempo constante.
• Acessar elementos em um array (por índice) ou objeto (por chave) é um tempo constante.
• Para um loop, a complexidade é o comprimento do loop multiplicado pela complexidade do que acontece dentro do loop.

Complexidade Espacial

Embora tenhamos nos concentrado na complexidade do tempo, também é possível calcular a complexidade do espaço (memória) usando Big O. Algumas pessoas incluem o tamanho da entrada em seus cálculos, mas geralmente é mais útil focar apenas no espaço exigido pelo algoritmo em si.

Regras para Complexidade Espacial (baseadas em JavaScript):

• A maioria dos valores primitivos (booleanos, números, etc.) são espaços constantes.
• Strings requerem espaço O(n) (onde n é o comprimento da string).
• Os tipos de referência (matrizes, objetos) são geralmente O(n), onde n é o comprimento da matriz ou o número de chaves no objeto.

Um exemplo

function sum(arr) {
    let total = 0;
    for (let i = ; i 



Nesta função, a complexidade do espaço é O(1) porque usamos uma quantidade constante de espaço (duas variáveis), independentemente do tamanho da entrada.

Para uma função que cria um novo array:



function double(arr) {
    let newArr = [];
    for (let i = 0; i 



Aqui, a complexidade do espaço é O(n) porque alocamos espaço para um novo array que cresce com o tamanho do array de entrada.


  
  
  Conclusão


Big O Notation fornece uma estrutura para analisar a eficiência de algoritmos de uma forma que é independente do hardware e de detalhes específicos de implementação. Compreender esses conceitos é crucial para o desenvolvimento de código eficiente, especialmente à medida que o tamanho dos dados aumenta. Ao se concentrar em como o desempenho é dimensionado, os desenvolvedores podem fazer escolhas informadas sobre quais algoritmos usar em seus aplicativos.