Big-O: como medir a eficiência dos seus algoritmos

O Big-O é um conceito fundamental na ciência da computação que nos ajuda a entender o desempenho dos algoritmos. Em termos simples, o Big-O nos ajuda a medir a rapidez com que um algoritmo cresce à medida que o tamanho da entrada aumenta. Essa medida nos permite comparar a eficiência de diferentes algoritmos e selecionar a melhor opção para uma determinada tarefa.

Compreendendo o Big-O

O Big-O é representado por uma função matemática que descreve o crescimento do tempo de execução do algoritmo em relação ao tamanho da entrada. O Big-O nos dá uma ideia geral da eficiência do algoritmo e nos ajuda a prever o tempo de execução com base no tamanho da entrada.

Por exemplo, um algoritmo com tempo de execução O(n) cresce linearmente à medida que o tamanho da entrada aumenta. Isso significa que, se o tamanho da entrada for dobrado, o tempo de execução também será dobrado.

Exemplo da notação O-grande: f(x) ∈ O(g(x)) de forma que existem c > 0 (e.g., c = 1) e x0 (e.g., x0 = 5) tal que f(x) ≤ cg(x) sempre que x ≥ x0 – Fonte: Wikipedia

Por outro lado, um algoritmo com tempo de execução O(n²) cresce exponencialmente à medida que o tamanho da entrada aumenta. Isso significa que, se o tamanho da entrada for dobrado, o tempo de execução será quadruplicado.

Exemplos de Big-O

Veja alguns exemplos de algoritmos com seus respectivos Big-Os:

O(1): algoritmos de tempo constante, como acessar um elemento em um array ou fazer uma operação matemática simples:

C#
public static T AccessFirstElement<T>(T[] array)
{
    return array[0];
}

// Fonte: Chat GPT
Java
public static <T> T accessFirstElement(T[] array) {
    return array[0];
}

// Fonte: Chat GPT
Python
def access_first_element(array):
    return array[0]

# Fonte: Chat GPT

O(n): algoritmos de tempo linear, como percorrer um array ou lista:

C#
void PrintList(int[] array)
{
    foreach (int item in array)
    {
        Console.WriteLine(item);
    }
}

// Fonte: Chat GPT
Java
void printList(int[] array) {
    for (int item : array) {
        System.out.println(item);
    }
}

// Fonte: Chat GPT
Python
def print_list(array):
    for item in array:
        print(item)

# Fonte: Chat GPT

O(n log n): algoritmos de tempo quase-linear, como mergesort e quicksort:

C#
public static int[] MergeSort(int[] array)
{
    if (array.Length <= 1)
    {
        return array;
    }

    int mid = array.Length / 2;
    int[] left = array.Take(mid).ToArray();
    int[] right = array.Skip(mid).ToArray();

    return Merge(MergeSort(left), MergeSort(right));
}

public static int[] Merge(int[] left, int[] right)
{
    int[] result = new int[left.Length + right.Length];
    int i = 0, j = 0, k = 0;

    while (i < left.Length && j < right.Length)
    {
        if (left[i] <= right[j])
        {
            result[k++] = left[i++];
        }
        else
        {
            result[k++] = right[j++];
        }
    }

    while (i < left.Length)
    {
        result[k++] = left[i++];
    }

    while (j < right.Length)
    {
        result[k++] = right[j++];
    }

    return result;
}

// Fonte: Chat GPT
Java
public static int[] mergeSort(int[] array) {
    if (array.length <= 1) {
        return array;
    }
    
    int mid = array.length / 2;
    int[] left = mergeSort(Arrays.copyOfRange(array, 0, mid));
    int[] right = mergeSort(Arrays.copyOfRange(array, mid, array.length));
    
    return merge(left, right);
}

public static int[] merge(int[] left, int[] right) {
    int[] result = new int[left.length + right.length];
    int i = 0, j = 0, k = 0;

    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            result[k++] = left[i++];
        } else {
            result[k++] = right[j++];
        }
    }

    while (i < left.length) {
        result[k++] = left[i++];
    }

    while (j < right.length) {
        result[k++] = right[j++];
    }

    return result;
}

// Fonte: Chat GPT
Python
def merge_sort(array):
    if len(array) <= 1:
        return array
    
    mid = len(array) // 2
    left = merge_sort(array[:mid])
    right = merge_sort(array[mid:])
    
    return merge(left, right)

# Fonte: Chat GPT

O(n²): algoritmos de tempo quadrático, como bubble sort e selection sort:

C#
public static int[] BubbleSort(int[] array)
{
    int n = array.Length;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n - i - 1; j++)
        {
            if (array[j] > array[j + 1])
            {
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
    return array;
}

// Fonte: Chat GPT
Java
public static int[] bubbleSort(int[] array) {
    int n = array.length;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (array[j] > array[j + 1]) {
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
    return array;
}

// Fonte: Chat GPT
Python
def bubble_sort(array):
    n = len(array)
    for i in range(n):
        for j in range(0, n-i-1):
            if array[j] > array[j+1]:
                array[j], array[j+1] = array[j+1], array[j]
    return array

# Fonte: Chat GPT

Escolhendo o melhor algoritmo

Como você pode ver, o Big-O é um conceito poderoso que nos permite comparar e escolher algoritmos com base em sua eficiência. Ao escolher um algoritmo, é importante considerar o tamanho da entrada e como ele afetará o tempo de execução.

Por exemplo, se você tiver um grande conjunto de dados para classificar, seria mais eficiente usar o mergesort (O(n log n)) do que o bubble sort (O(n²)). No entanto, se o conjunto de dados for pequeno, a diferença de tempo de execução entre os algoritmos pode ser insignificante.

Esse conteúdo é parte do material disponibilizado para os participantes do meu grupo de estudos de Algoritmos e Estruturas de Dados. Se você se interessou pelo tema, conheça também o meu curso de Introdução à Análise de Algoritmos e Big-O.

Quer se aprofundar neste tema?

Então participe do grupo de estudos de Algoritmos e Estruturas de Dados.

Domine algoritmos e estruturas de dados, torne-se um desenvolvedor de software “além do básico” e diferencie-se no mercado.

Participe do
grupo intensivo de

Algoritmos e Estruturas de Dados

com

Domine algoritmos e estruturas de dados, torne-se um desenvolvedor de software “além do básico” e diferencie-se no mercado.

Participe do
grupo intensivo de

Algoritmos e Estruturas de Dados

com

Domine algoritmos e estruturas de dados, torne-se um desenvolvedor de software “além do básico” e diferencie-se no mercado.

Veja outros artigos relacionados

O Código de Huffman: Uma Transcrição Explicativa

A compressão de dados é um assunto que fascina pela sua capacidade de transformar a maneira como armazenamos e transferimos...

A Relação entre Programação Funcional e Concorrência

A programação funcional vem ganhando espaço na comunidade de tecnologia. Por que isso acontece? Este artigo explora essa popularidade, focando...

Nomes Assustadores para Conceitos Simples

No mundo da tecnologia e da computação, frequentemente nos deparamos com termos que parecem complexos e intimidantes. Vou compartilhar uma...

Crie sua conta

Preencha os dados a seguir para iniciar o seu cadastro no Grupo Intensivo de Estudos de DDD do Jeito Certo:

Crie sua conta

Preencha os dados a seguir para iniciar o seu cadastro no Grupo Intensivo de Estudos de Reputação e Marketing Pessoal:

Crie sua conta

Preencha os dados a seguir para iniciar o seu cadastro no Grupo Intensivo de Estudos de Reputação e Marketing Pessoal:

Crie sua conta

Preencha os dados a seguir para iniciar o seu cadastro no Grupo Intensivo de Estudos de Padrões de Projeto:

Crie sua conta

Preencha os dados a seguir para iniciar o seu cadastro no Grupo Intensivo de Estudos de Padrões de Projeto:

Crie sua conta

Preencha os dados a seguir para iniciar o seu cadastro no Grupo Intensivo de Estudos de Algoritmos e Estruturas de Dados:

Crie sua conta

Preencha os dados a seguir para iniciar o seu cadastro no Grupo Intensivo de Estudos de Algoritmos e Estruturas de Dados:

Crie sua conta

Preencha os dados a seguir para iniciar o seu cadastro no Programa ElemarJR de Aceleração, Do Jeito Certo:

Crie sua conta

Preencha os dados a seguir para iniciar o seu cadastro no Programa ElemarJR de Aceleração, Do Jeito Certo:

Crie sua conta

Preencha os dados a seguir para iniciar o seu cadastro no Grupo Intensivo de Estudos de Reputação e Marketing Pessoal:

Crie sua conta

Preencha os dados a seguir para iniciar o seu cadastro no Grupo Intensivo de Estudos de Reputação e Marketing Pessoal:

Crie sua conta

Preencha os dados a seguir para iniciar o seu cadastro no Grupo Intensivo de Estudos de Padrões de Projeto:

Crie sua conta

Preencha os dados a seguir para iniciar o seu cadastro no Grupo Intensivo de Estudos de Padrões de Projeto:

Crie sua conta

Preencha os dados a seguir para iniciar o seu cadastro no Grupo Intensivo de Estudos de DDD do Jeito Certo:

Crie sua conta

Preencha os dados a seguir para iniciar o seu cadastro no Grupo Intensivo de Estudos de DDD do Jeito Certo:

Crie sua conta

Preencha os dados a seguir para iniciar o seu cadastro no Grupo Intensivo de Estudos de Algoritmos e Estruturas de Dados:

Crie sua conta

Preencha os dados a seguir para iniciar o seu cadastro no Grupo Intensivo de Estudos de Algoritmos e Estruturas de Dados:

Mentoria em Arquitetura de Software

Ênfase em Systems Design

Para se candidatar nesta turma aberta, preencha o formulário a seguir:

Reproduzir vídeo

Crie sua conta

Preencha os dados a seguir para iniciar o seu cadastro no curso de Big-O: como medir a eficiência dos seus algoritmos:

Crie sua conta

Preencha os dados a seguir para iniciar o seu cadastro no curso de Big-O: como medir a eficiência dos seus algoritmos:

Big-O: como medir a eficiência dos seus algoritmos

Crie sua conta

Preencha os dados a seguir para iniciar o seu cadastro no Grupo Intensivo de Estudos de Reputação e Marketing Pessoal:

Crie sua conta

Preencha os dados a seguir para iniciar o seu cadastro no curso de Big-O: como medir a eficiência dos seus algoritmos:

Crie sua conta

Preencha os dados a seguir para iniciar o seu cadastro no Grupo Intensivo de Estudos de DDD do Jeito Certo:

Crie sua conta

Preencha os dados a seguir para iniciar o seu cadastro no Grupo Intensivo de Estudos de Padrões de Projeto:

Crie sua conta

Preencha os dados a seguir para iniciar o seu cadastro no Grupo Intensivo de Estudos de Algoritmos e Estruturas de Dados:

× Precisa de ajuda?