Forem: Rafael Serinolli

Big O Notation

Rafael Serinolli — Tue, 26 Mar 2024 20:07:54 +0000

What is Big O?

"Big O" is a notation used to measure the efficiency of an algorithm in terms of execution time or memory usage, also known as complexity.

How does it work?

In simple terms, Big O describes how the execution time (or memory usage) grows as the input data size (represented by the letter n) increases.

Main complexity classes

Constant Complexity

Representation: O(1)
The algorithm's cost is independent of the size of n. Instructions are executed a fixed number of times.

// Regardless of the size of the array, 
// the instruction is executed only once
public static int example1(int[] array) {
    return array[array.length / 2];
}

Linear Complexity

Representation: O(n)
The algorithm's cost grows linearly with the input size. Each input element needs to be processed once.

// This algorithm iterates through each element of the array once, summing the values.
public static int example2(int[] array) {
    int sum = 0;
    for (int i = 0; i < array.length; i++) {
        sum += array[i];
    }
    return sum;
}

Quadratic Complexity

Representation: O(n²)
The algorithm's cost increases quadratically with the size of n. It typically occurs when there are two nested loops.

// This algorithm implements a sorting method, the Bubble Sort
public static void bubbleSort(int[] array) {
    int temp;
    for (int i = 0; i < array.length - 1; i++) {
        for (int j = 0; j < array.length - i - 1; j++) {
            if (array[j] > array[j + 1]) {
                temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
}

Logarithmic Complexity

Representation: O(log n)
The algorithm's cost grows logarithmically with the size of n. It is common in search algorithms or divide and conquer algorithms.

// This algorithm performs a binary search on a SORTED array
public static int example4(int[] array, int key) {
    int left = 0;
    int right = array.length - 1;
    while (left <= right) {
        int middle = left + (right - left) / 2;
        if (array[middle] == key) {
            return middle;
        }
        if (array[middle] < key) {
            left = middle + 1;
        } else {
            right = middle - 1;
        }
    }
    return -1;
}

Complexity and Optimization

The following graph demonstrates, in terms of time and memory efficiency, which complexities perform better as input parameters tend to infinity:

^{Graph: https://www.geeksforgeeks.org/analysis-algorithms-big-o-analysis/}

Big O Notation

Rafael Serinolli — Tue, 26 Mar 2024 19:50:06 +0000

O que é Big O?

"Big O" é uma notação usada para medir o custo de um algoritmo em termos de tempo de execução ou uso de recursos como o espaço de memória, também conhecidos como complexidade.

Como funciona?

Em termos simples, a notação descreve como o tempo de execução (ou espaço de memória) cresce à medida que os dados de entrada (representados pela letra n) aumentam.

Principais classes de complexidade

Complexidade constante

Representação: O(1)
O custo do algoritmo independe do tamanho de n. As instruções são executadas um número fixo de vezes.

// Independentemente do tamanho do vetor, 
// a instrução é executada uma única vez
public static int exemplo1(int[] vetor) {
    return vetor[vetor.length / 2];
}

Complexidade linear

Representação: O(n)
O custo do algoritmo cresce linearmente com o tamanho de n. Cada elemento de entrada precisa ser processado uma vez.

// Este algoritmo percorre cada elemento do vetor uma vez, somando os valores
public static int exemplo2(int[] vetor) {
    int soma = 0;
    for (int i = 0; i < vetor.length; i++) {
        soma += vetor[i];
    }
    return soma;
}

Complexidade quadrática

Representação: O(n²)
O custo do algoritmo aumenta quadraticamente com o tamanho de n. Normalmente ocorre quando há dois loops aninhados.

// Este algoritmo implementa um método de ordenação, o Bubble Sort
public static void bubbleSort(int[] vetor) {
    int temp;
    for (int i = 0; i < vetor.length - 1; i++) {
        for (int j = 0; j < vetor.length - i - 1; j++) {
            if (vetor[j] > vetor[j + 1]) {
                temp = vetor[j];
                vetor[j] = vetor[j + 1];
                vetor[j + 1] = temp;
            }
        }
    }
}

Complexidade logarítmica

Representação: O(log n)
O custo do algoritmo cresce de forma logarítmica com o tamanho de n. É comum em algoritmos de busca ou de divisão e conquista.

// Este algoritmo realiza uma busca binária em um vetor ORDENADO
public static int exemplo4(int[] vetor, int chave) {
    int esquerda = 0;
    int direita = vetor.length - 1;
    while (esquerda <= direita) {
        int meio = esquerda + (direita - esquerda) / 2;
        if (vetor[meio] == chave) {
            return meio;
        }
        if (vetor[meio] < chave) {
            esquerda = meio + 1;
        } else {
            direita = meio - 1;
        }
    }
    return -1;
}

Complexidade e otimização

O gráfico à seguir demonstra, em termos de eficiência de tempo e memória, quais complexidades apresentam melhor desempenho quando os parâmetros de entrada tendem ao infinito:

^{Gráfico: https://www.geeksforgeeks.org/analysis-algorithms-big-o-analysis/}

Angular Signals

Rafael Serinolli — Mon, 29 May 2023 18:55:18 +0000

O Angular Framework oficialmente chegou em sua versão 16 e alguns novos recursos interessantes foram adicionados. Neste tópico, falaremos sobre um deles: os Signals. Vamos desmistificar o assunto e entender como aplicar esse recurso capaz de melhorar a velocidade de sua aplicação de maneira simplificada.

Índice

Entendendo os Signals
Sintaxe
Funções set, update e mutate
Função effect
Conclusão

Entendendo os Signals

Assim como uma variável, um Signal armazena um valor que pode ser alterado conforme a vontade do desenvolvedor. Contudo, diferentemente de uma variável, um Signal consegue identificar os lugares e componentes de uma aplicação que usam o seu valor, emitindo um sinal para estes quando houver alterção.

Exemplificando de maneira muito simples, imagine que você está desenvolvendo um sistema de vendas e possui 3 variáveis declaradas: ValorProdutoUnitário, QuantidadeVendas e ValorBruto.

export class Vendas {
valorProdutoUnitario: number = 10;

quantidadeVendas: number = 15;

valorBruto: number = 150;
}

Caso o valor unitário ou a quantidade de vendas mude, é necessário realizar as demais mudanças manualmente, com funções que sejam executadas em eventos para adequar o sistema. Com os Signals, podemos dinamizar não só este processo, mas também muitos outros.
Quando um Signal é alterado, ele emite um sinal para que os componentes que o referenciam, fazendo assim com que atualizem seu valor.

Sintaxe

Como declarar e referenciar um Signal.

Declarando

import { signal } from '@angular/core';
//[...]
//Declarando um Signal. Seu valor inicial é o de dentro do parêntesis
quantidadeVendas = signal(15);
valorProdutoUnitario = signal(10);

Referenciando

//Para que o valor do Signal seja acessível, deve-se 
//colocar os parêntesis. Exatamente como uma função.
console.log(this.quantidadeVendas());

Signals dependentes

Cria-se um Signal à partir de outro

import { computed } from '@angular/core';
//Neste caso, quando a quantidade de vendas ou o preço 
//unitário mudarem, o valor bruto será atualizado automaticamente.
valorBruto = computed(() => 
  this.quantidadeVendas() * this.valorProdutoUnitario()
);

Alterando um Signal

set

Atribui diretamente um novo valor ao Signal e notifica os dependentes

this.valorProdutoUnitario.set(10);
console.log(this.valorProdutoUnitario());
//10

update

Atualiza o valor do Signal baseado no valor atual. Recebe uma função de callback, onde o retorno é o novo valor do Signal.

this.valorProdutoUnitario.update(() => 100);
console.log(this.valorProdutoUnitario());
//100
this.valorProdutoUnitario.update((b) => b + 100);
console.log(this.valorProdutoUnitario());
//200

mutate

Usado principalmente com arrays. Modifica o conteúdo do valor de um Signal, não o valor como um todo. Ex: elementos de um array.

this.objetoExemplo.mutate(i => i.preco = i.preco + (i.preco * .20));
//Altera a propriedade "preco" do objetoExemplo, adicionando 20% de seu valor.

Effect

Possibilita a execução de uma função toda vez que um Signal sofrer alteração.

import { effect } from '@angular/core';
//Ao início do componente em questão, define que devemos 
//logar valor do Signal no console quando alterado
ngOnInit(): void {
  effect(() => {
     console.log(this.valorProdutoUnitario());
  });
}

Assim, sempre que alterado, o novo valor de valorProdutoUnitario será logado no console do navegador.

Conclusão

Estes novos recursos possibilitam um código mais dinâmico e menos poluído, visto que retiram a necessidade de atualizar valores dependentes manualmente, diminuindo a quantidade de linhas de código escritas, aumentando a performance e simplificando o desenvolvimento.