Olá, jovens, seguindo a sequência de artigos sobre algoritmos hoje vamos entender como funciona o cálculo para descobrir a complexidade referente a utilização de recursos, entender o quanto de esforço seu algoritmo faz para resolver um problema dado uma entrada X? Vamos responder essa pergunta na sequência.

Antes de sair definindo variáveis e funções, vamos definir o contexto, se você já programou ou está iniciando pode ficar confuso com algumas palavras que irei utilizar para realizar o cálculo, então sempre que falar operação, estou referindo a atribuição/definição de variáveis ou até mesmo condicionais (if/else), quando falar em interação/loop estou me referindo a laços de repetição.

Agora vamos para pesos, uma operação tem peso constante, ou seja, atribuir um valor a uma variável ou verificar um condicional, então irei utilizar o valor 1, para representar a constante. Já a interação irei utilizar uma variável, que chamarei N, que vai ser representada em um somatório conforme sua interação. (Se ficou preocupado não esqueça que no final o que queremos é a ordem de grandeza da função, constantes 1 ou 100 no final não interfere no resultado para notação do Big O).

Bom, agora a definição do problema que vamos resolver:

Dado uma lista de inteiros ordenada, desenvolva uma função que dado um número x realiza uma busca do número na lista ordenada e caso encontre o valor retorne à posição (índice) do valor na lista, e caso não encontre retorne -1.

def buscar_numero_na_lista(lista, x): # definição da função
    for i in range(len(lista)): # loop
        if lista[i] == x: # operação de condição
            return i # retorno do índice caso encontre
    return -1 # retorno -1 caso não encontre

O número de operações de interação é proporcional a posição do número x na lista, ou caso não exista o tamanho da lista. Lembrando que escolhemos o pior caso para definir a complexidade, logo temos n (interações) * 1 (Operações de condicionais constantes), então a função da complexidade fica f(n) = n*1, onde N séria a entrada (lista de números ordenada), por fim o Big O, O(n).

Abaixo, um exemplo de código usando busca binária para resolver o mesmo problema.

def busca_binaria(lista, x): # definição da função
    left = 0 # operação de variável
    right = len(lista) – 1 # operação de variável

    while left <= right: # loop
        mid = (left + right) // 2 # operação de variável

        if lista[mid] == x: # operação de condição
            return mid
        elif lista[mid] < x: # operação de condição
            left = mid + 1
        else: # operação de condição
            right = mid - 1

    return -1

Vamos lá, pega papel e caneta aí para não se perder… 2 (definição das variáveis left e rigth) + log n (definição do loop while left <= right:) * 3 (máximo de operações básicas executadas dentro do loop). Você deve estar se perguntando, se é um loop while, porque no exemplo anterior o loop foi n e agora é log n, bom, vale relembrar que sempre olhamos para o pior caso, seguindo o mesmo exemplo acima, procurar um valor que não pertence a lista passada. O loop nesse caso tem um comportamento diferente ao anterior, ele não vai de 0 até n, sequencialmente, ele vai quebrando a lista pela metade em cada rodada, n/2, n/4, n/8 e assim por diante. Em outras palavras, dado uma entrada n (onde n é o tamanho da lista ordenado), temos, f(n) = 2 + 3 * log n, logo, O(log n).

Para quem curte matemática, vamos demostrar essa mágica do O (log n), a pergunta que devemos fazer e a seguinte, qual o número de divisões da lista são necessárias para chegar a um único elemento? (para qualquer elemento em qualquer lista, ok), chegamos na equação n/2^x = 1, onde o x representa o número de divisões e n o tamanho da lista, essa mesma função pode ser reescrita da seguinte forma, f(n) = log2(n), logo temos que O (log n). Se ainda não ficou claro que a busca binária é mais rápida que a busca sequencial, vamos para um exemplo prático. Imagine que você tem uma lista com 1024 números, ordenados de 1 a 1024. E você deseja buscar o número 1000. Usando a busca sequencial, primeira função, levaria 1000 interações, porque ele vai começar do 1 até chegar no último, 1000 e retornar o índice.

Já a busca binária, levaria apenas 10 interações para encontrar o índice. Isso para um exemplo simples, é pequeno, imagine escalas maiores, uma função bastante requisitada, quanta diferença faria. Espero que tenham gostado, em breve irei trazer mais artigos sobre algoritmos.