Como calcular Complexidade de Algoritmo na prática

Last updated on 31 de janeiro de 2024

Estamos em plena ascensão da evolução computacional. Já estamos no mundo do Big Data, em meio a uma revolução no que tange o uso de Inteligência Artificial para fazer diversas ações de forma autônoma. Enfim… A área de programação segue naturalmente essa evolução, e conhecimentos mais especializados são necessários para você não ficar para trás na competição de uma vaga para o mercado de trabalho. 

Algumas empresas, como o próprio Facebook, avalia o quão adaptativo é o profissional e o quanto ele conhece sobre programação no geral. Por isso, não convém você apostar todas as suas cartas em focar na sua linguagem de programação X ou Y “preferida“. Outros fatores como capacidades de inter relacionamentos pessoais e conhecer sobre algoritmos de forma mais profunda é o que vai importar na decisão de qual profissional contratar. Por esse motivo, estou preparando essa série de artigos, para te mostrar que existem diversas formas de resolver um mesmo problema e o que vai definir qual algoritmo você deve utilizar, vai ser qual o volume da sua entrada, quantos passos o seu algoritmo precisou para resolver esse problema. Para isso, você precisa entender definitivamente como analisar a complexidade de um algoritmo. Se você ainda não está familiarizado com o tema, veja o artigo Análise de Complexidade de Algoritmos.

No artigo anterior, já fizemos um pequeno ensaio para te mostrar como fazer esse cálculo, mas não é suficiente para você dominar o assunto. Vamos fazer mais alguns exemplos e cálculos passo a passo. Se você não tem uma boa base de matemática não se preocupe, veja também o artigo O que um programador precisa saber sobre matemática?. Além disso, conhecer sobre estruturas de dados é pré-requisito. Veja também o artigo Estruturas de Dados: Listas, Filas, Pilhas, Conjuntos, Árvores e Hash Tables.

Como determinar a ordem de complexidade de um algoritmo?

Podemos definir qual algoritmo é preferível para resolver determinado problema de duas formas: empírica (implementar o algoritmo e testá-lo para diferentes instâncias, ou seja, em função da sua entrada, n) e teórica (determinar matematicamente a quantidade de operações realizadas pelos algoritmos como função do tamanho da instância considerada).

Para desempatar o jogo entre empírico e teórico, entra em cena, a notação Big O (leia-se grande ó, Big oh), que é muito utilizada para expressar comparativamente a velocidade que uma função tende ao infinito. Ou seja, ficamos de olho no comportamento do algoritmo a medida em que aumentamos os seus valores  de entrada, criamos com isso a função de Tempo de execução do Algoritmo, onde T(n) = O(n) ou T(n) = O(f(n))

Para os amantes das definições matemáticas, temos: T(n) é de ordem f(n) se e somente se existem constantes positivas c e n0 tal que T(n) ≤ c.f(n) para todo  n > n0

Um dos recursos da programação que você tem que observação, são os laços de repetições, como exemplo o laço FOR. Considere o código a seguir:

for (int i=0; i < n; i++) {
    // instruções
}

Podemos contabilizar que esse laço vai ser executado n vezes e em cada interação — em cada volta que o laço executar — temos um número constante de instruções, ou seja, já sabemos exatamente quanto vale o valor de n, e esse valor não vai mudar (é constante). Chamamos de complexidade linear, que é representada por O(n). 

Agora veja o seguinte código utilizando um FOR dentro de outro FOR (chama-se FOR aninhado). Observe que nesse exemplo, o n também é constante, porém a cada interação do primeiro laço o segundo laço é executado n vezes, com isso temos n x n,  que é o mesmo que n². Com isso encontramos uma complexidade quadrática, que é representada por O(n²).

for (int i=0; i < n; i++) {
    for (int j=0; j < n; j++) {
        // instruções   
    }
}

Se você observar, essa é a mesma complexidade do algoritmo Bubble sort, que mostrei no artigo anterior. Aqui você já pode deduzir que se você colocar mais um FOR aninhado, teremos uma complexidade cúbica, O(n³)  

Como colocar em prática esses conceitos de complexidade de algoritmo no mundo real?

Imagine que você tem um algoritmo, responsável por pegar uma subsequência máxima de um arranjo, por exemplo [-2, 11, -4, 13, -5, 2] e encontrar sua soma máxima. Para esse exemplo, a soma da subsequência máxima é [11, -4, 13] = 20. Veja o primeiro algoritmo que tem complexidade cúbica:

public class MaxSub {
    public static int sum(int[] a) {
        int maxSum = 0;
        for (int i = 0; i < a.length; i++) {
            for (int j = i; j < a.length; j++) {
                int sum = 0;
                for (int k = i; k <= j; k++) sum += a[k];
                if (sum > maxSum) maxSum = sum;
            }
        }
        return maxSum;
    }
}

Imagine se colocássemos um array muito maior que esse com tamanho n=6… Teríamos um péssimo desempenho, uma vez que esse algoritmo tem complexidade cúbica, O(n³) . Vamos pegar esse mesmo problema e resolver ele reduzindo para uma complexidade quadrática, O(n²):

public class MaxSub {
    public static int sum(int[] a) {
        int maxSum = 0;
        for (int i = 0; i < a.length; i++) {
            int sum = 0;
            for (int j = i; j < a.length; j++) {
                sum += a[j];
                if (sum > maxSum) {
                    maxSum = sum;
                }    
            }
        }
        return maxSum;
    }
}

Se você observar, para poucos valores de entrada, é quase imperceptível medir o desempenho dessas duas implementações. Agora que você sabe que o primeiro tem complexidade cúbica e o segundo quadrática, se seu n fosse igual a 500? Teríamos algo em torno de O(n²) = 250.000, enquanto O(n³) = 125.000.000. E se o n fosse 100 mil? Faça a conta kkk! Consegue perceber a importância de saber calcular a complexidade dos algoritmos?

Pegando um programa grande e dividindo em problemas menores

Às vezes encontramos problemas grandes e somos obrigados a, ou fracionar esse problema dividindo-o em subproblemas menores (O(n log n)) ou simplesmente transformando-os em problemas menores (O(log n)). Entra em evidência aqui a complexidade logarítmica. Agora você deve estar assustado com esse negócio de logaritmo, né? kkkk Calma que vou explicar! A lógica para se calcular logaritmos é simples, mas primeiro você tem que entender a anatomia de um logaritmo, log_a^b = x, resumidamente a = base do logaritmo, b = logaritmando e x = logaritmo. Então você pega o a eleva à x e o seu resultado vai ser  b, assim: a^x = b.

Certamente você vai encontrar esses tipos de situações em algoritmos de busca, como é o caso do algoritmo de Busca Binária (para esse exemplo estamos supondo que o arranjo está ordenado). Veja:

public class BinarySearch {
    public static int searchInteractive(int[] a, int key) {
        int low = 0;
        int high = a.length - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (key < a[mid]) {
                high = mid - 1;
            } else if (key > a[mid]) {
                low = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }
}

public class BinarySearchTest {
    public static void main(String[] args) {
        int[] test = {1, 3, 4, 55, 104, 222, 229, 300};
        System.out.println(BinarySearch.searchInteractive(test, 55));
    }
}

Esse programa faz uma iteração que recebe um arranjo de tamanho N, depois N/2, depois N/4, e assim sucessivamente, logo temos a complexidade logarítmica O(log n).

Repetindo, no exemplo da busca binária, implementamos o algoritmo supondo que o arranjo de dados estava ordenado. Existem algoritmos especializados exclusivamente e efetuar ordenações e eles também tem sua medição de complexidade. Vamos ver como é a complexidade de um algoritmo de ordenação, como o QuickSort. Esse algoritmo é muito utilizado porque ele tem pior caso O(N² ) e no melhor caso O(N log N), além de não exigir armazenamento adicional. Isso é perfeito para arranjos não ordenados.

public class QuickSort {

    public static void quickSort(int[] arr, int low, int high) {
        if (arr == null || arr.length == 0) return;
        if (low >= high) return;

        // pick the pivot
        int middle = low + (high - low) / 2;
        int pivot = arr[middle];

        // make left < pivot and right > pivot
        int i = low, j = high;
        while (i <= j) {
            while (arr[i] < pivot) {
                i++;
            }

            while (arr[j] > pivot) {
                j--;
            }

            if (i <= j) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++;
                j--;
            }
        }

        // recursively sort two sub parts
        if (low < j)
            quickSort(arr, low, j);

        if (high > i)
            quickSort(arr, i, high);
    }
}

O algoritmo QuickSort utiliza o paradigma de programação Dividir para Conquistar ou divide and conquer. Esse paradigma é uma abordagem recursiva em que a entrada do algoritmo é ramificada múltiplas vezes a fim de quebrar o problema maior em problemas menores da mesma natureza. É por esse fator, que no melhor cenário, esse algoritmo tem complexidade n Log n, isso considerando o custo com pivô cuja posição correta (final) seja o meio do vetor. Funciona assim:  o vetor de tamanho n é dividido ao meio, cada metade é dividida ao meio, …, m vezes => n = 2m, logo, m =  log₂ n. Com isso, cada parte do vetor realizam n comparações, ou seja, cada metade é igual a n * m,  deste modo chegamos ao custo de 2 * (n * m) que é igual a O(n log₂ n).

Qual a maior complexidade que podemos encontrar em nossos algoritmos?

Não preciso de muito esforço para lhe mostrar qual a pior complexidade que você pode encontrar em um algoritmo, basta dar uma analisada no gráfico a seguir:

Observe que os “campeões da destruição de sonhos” são os que envolvem complexidades exponenciais O(2n ) e O(n!).. Um Algoritmo com complexidade exponencial, normalmente não são úteis sob o ponto de vista prático. Imagine o seguinte, se você definisse o n como 20, o tempo de execução chegaria a cerca de um milhão. Ou seja, isso é tido como totalmente  intratáveis. Só a título de curiosidade, você vai encontrar essa complexidade exponencial em algoritmos que tentam resolver o Problema do Caixeiro Viajante,

Esse tema é fantástico! Muito bom!!! Esses dois artigos publicados na sequência, já vão te dar uma visão muito boa sobre como analisar as complexidades dos seus algoritmos. Obviamente, o tema é muito mais abrangente, mas acredito que essa base está bastante completa e vai te levar a outro nível como programador. Vou deixar logo abaixo referências de livros, caso você queira se aprofundar mais no assunto.

Se você esta vendo este artigo, significa que você já chegou a um patamar mais elevado no mundo da programação, já está na hora de você se aprofundar em conceitos mais importantes como qualidade de código e padrões de projetos.

Escrevi o livro “Além do Código” para desenvolvedores que querem ser mais do que meros codificadores. É um guia completo que aborda todos esses tópicos avançados de forma prática e didática.

Se você está realmente comprometido em não ficar para trás, não perca tempo e adquira agora.

Confiança Sempre!!!

Fontes: 

• https://web.fe.up.pt/~rcamacho/cadeiras/bioinformatica/docs/algoritmos.pdf
• https://www.blogcyberini.com/2017/09/busca-binaria.html
• http://www.faccamp.br/osvaldo/SequenciasConjuntos.pdf
• https://joaoarthurbm.github.io/eda/posts/quick-sort/
• https://www.di.ubi.pt/~desousa/2012-2013/CS/complexidade_computacional_jsp.pdf