Todo programa de computador que roda no seu dispositivo tem um conjunto específico de instruções, que são executadas em uma ordem específica para completar uma tarefa. A tarefa pode ser ordenar um conjunto de números, modificar uma imagem, controlar o estoque ou até mesmo executar seu videogame favorito. É aqui que os algoritmos entram em ação. Um algoritmo é um conjunto de instruções inequívocas para resolver um problema ou executar uma tarefa. Você pode pensar em algoritmos como "receitas". Quando você cozinha, as receitas listam todos os ingredientes que você vai precisar e fornecem instruções passo a passo sobre como preparar um prato. Equivalentemente, você pode pensar em algoritmos como "receitas" que dizem aos computadores exatamente o que deve ser feito e como fazer isso. Algoritmos têm duas características principais: * Eles não podem continuar indefinidamente. Eles devem terminar em um número finito de etapas. * Cada etapa deve ser precisa e inequívoca. Eles podem ter zero, um ou mais inputs e gerar uma ou mais outputs. As etapas de um algoritmo são independentes de qualquer linguagem de programação. Mas para realmente fazê-los rodar em um computador, você precisa implementá-los em uma linguagem de programação, como Python ou JavaScript. Se um algoritmo estiver correto, a saída para qualquer entrada válida deve corresponder à saída esperada. Além de serem corretos, os algoritmos também devem ser eficientes. A eficiência do algoritmo pode ser medida em termos de quanto tempo eles levam para executar e quanto espaço eles requerem na memória para completar a tarefa. Saber a eficiência de um algoritmo é muito importante porque isso dá uma ideia de quão bem ele irá performar conforme o tamanho da entrada cresce. Por exemplo, ordenar 15 inteiros não é o mesmo que ordenar 1 milhão de inteiros. À medida que o processo cresce em tamanho e complexidade, se o algoritmo não for eficiente o suficiente para lidar com isso, você pode acabar com um programa de computador muito lento que pode até travar o sistema inteiro. É por isso que é muito importante desenvolver e escolher os algoritmos mais eficientes possíveis. É aqui que a notação Big O se torna muito importante. A notação Big O descreve o desempenho no pior caso ou a taxa de crescimento de um algoritmo conforme o tamanho da entrada aumenta. A taxa de crescimento de um algoritmo refere-se a como os recursos que ele requer aumentam conforme o tamanho da entrada cresce. A notação Big O foca no desempenho no pior caso porque esse caso é muito importante para entender quão eficiente o algoritmo pode ser, mesmo no pior cenário, independentemente da entrada. Voltando ao nosso exemplo de ordenação, ordenar 1 milhão de inteiros deve intuitivamente levar mais tempo e recursos do que ordenar 15 inteiros. Mas quanto mais? Isso realmente depende do algoritmo que você escolher para ordená-los. A notação Big O não fornecerá um número exato para descrever a eficiência do algoritmo, mas dará uma ideia de como ele escala conforme o tamanho da entrada cresce, com base no número de operações realizadas pelo algoritmo. Na notação Big O, geralmente denotamos o tamanho da entrada com a letra n. Por exemplo, se a entrada for uma lista, n indicaria o número de elementos nessa lista. Fatores constantes e termos de ordem inferior não são levados em conta para encontrar a complexidade de tempo de um algoritmo com base no número de operações. Isso acontece porque, à medida que o tamanho de n cresce, o impacto desses termos menores no número total de operações realizadas se tornará cada vez menor. O termo que dominará o comportamento geral do algoritmo será o termo de maior ordem com n, o tamanho da entrada. Por exemplo, se um algoritmo realiza 7n + 20 operações para ser concluído, o impacto da constante 20 no resultado final será cada vez menor conforme n cresce. O termo 7n tenderá a dominar e isso definirá o comportamento geral e a eficiência do algoritmo. Outro exemplo seria um algoritmo que leva 20n² + 15n + 7 operações para ser concluído. O termo 20n² tenderá a dominar conforme n cresce, então este algoritmo teria uma complexidade de tempo quadrática porque o termo dominante tem n². A complexidade de tempo quadrática é um dos muitos tipos diferentes de complexidades de tempo que você pode encontrar no mundo dos algoritmos. Vamos aprender sobre alguns dos mais comuns. O(1) é conhecido como "Complexidade de Tempo Constante". Quando um algoritmo tem complexidade de tempo constante, ele leva o mesmo tempo para executar, independentemente do tamanho da entrada. Por exemplo, verificar se um número é par ou ímpar sempre levará a mesma quantidade de tempo, independentemente do próprio número.

function checkEvenOrOdd(number) {
  if (number % 2 === 0) {
    return "Even";
  } else {
    return "Odd";
  }
}

O(log n) é conhecido como "Complexidade de Tempo Logarítmica". Isso significa que o tempo necessário pelo algoritmo aumenta lentamente conforme o tamanho da entrada cresce. Isso é comum em problemas nos quais o tamanho do problema é repetidamente reduzido por uma fração constante. Por exemplo, um algoritmo de busca popular chamado Binary Search tem complexidade de tempo no pior caso O(log n). Isso ocorre porque elimina metade dos elementos restantes em cada comparação, o que o torna mais eficiente no geral. O(n) é conhecido como "Complexidade de Tempo Linear". O tempo de execução de algoritmos com essa complexidade de tempo aumenta proporcionalmente ao tamanho da entrada. Por exemplo, um loop for que itera sobre todos os elementos de uma lista realizará mais iterações à medida que o número de elementos da lista aumenta. Se a lista for dobrada em tamanho, o número de operações também aproximadamente dobrará.

for (const grade of grades) { // grades is an array
  console.log(grade);
}

O(n log n) é conhecido como "Complexidade de Tempo Logarítmico-Linear". Esta é uma complexidade de tempo comum de algoritmos de ordenação eficientes, como Merge Sort e Quick Sort. O(n²) é conhecido como "Complexidade de Tempo Quadrática". O tempo de execução desses algoritmos aumenta quadraticamente em relação ao tamanho da entrada, o que geralmente não é eficiente para problemas do mundo real. Loops aninhados são um exemplo comum de complexidade de tempo quadrática. O loop interno realizará n iterações para cada uma das n iterações do loop externo, resultando em n ao quadrado de iterações.

for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    console.log("Hello, World!");
  }
}

Outras complexidades de tempo incluem "Complexidade de Tempo Exponencial", denotada como O(2^n) e "Complexidade de Tempo Fatorial", denotada como O(n!). Ambos são ineficientes para cenários do mundo real. Neste gráfico, você pode comparar o crescimento das funções matemáticas que representam as complexidades de tempo mais comuns. Pense no eixo x (horizontal) como o tamanho da entrada e no eixo y (vertical) como o tempo de execução do algoritmo. Você pode ver que a Complexidade de Tempo Quadrática (O(n²)) (amarelo) cresce muito mais rápido do que as outras, enquanto a Complexidade de Tempo Constante (O(1)) (vermelho) permanece constante, mesmo se a entrada aumentar. <img src="https://cdn.G.E.A.R ACADEMY.org/curriculum/lecture-transcripts/what-is-an-algorithm-and-how-does-big-o-notation-work-1.png" alt="graph comparing time complexity"> Ótimo. Até agora, você aprendeu sobre a notação Big O em termos de requisitos de tempo, mas essa notação também pode ser aplicada ao contexto de requisitos de espaço. Neste contexto, ele descreve como o espaço de memória requerido pelo algoritmo cresce à medida que o tamanho da entrada cresce. Algoritmos com "Complexidade de Espaço Constante" O(1) sempre requerem uma quantidade constante de espaço de memória, mesmo quando a entrada aumenta. Um exemplo seria um algoritmo que apenas cria e armazena algumas variáveis na memória. Em contraste, o espaço necessário para algoritmos com "Complexidade de Espaço Linear" O(n) aumenta proporcionalmente conforme o tamanho da entrada cresce. Um exemplo disso seria um algoritmo que cria e armazena uma cópia de uma lista de comprimento n. E finalmente, os requisitos de espaço de um algoritmo com "Quadratic Space Complexity" O(n²) aumentam quadraticamente conforme o tamanho da entrada cresce. Um exemplo disso seria criar uma matriz 2D, onde as dimensões são determinadas pelo tamanho da entrada, armazenando todos os pares possíveis. Algoritmos são os blocos de construção dos programas de computador, enquanto a notação Big O é uma estrutura poderosa para analisar quão eficientes eles são, com base em como seus requisitos de tempo e espaço no pior cenário escalam à medida que o tamanho da entrada cresce. Entender a eficiência deles é muito importante para desenvolver software que funcione eficientemente em cenários do mundo real.