Big O Notation

Big O Notation

• Não é uma necessariamente sobre performance

• Diz respeito a escalabilidade e não necessariamente a performance

• Uma abordagem para de notação de performance

• Em situações onde temos poucos registro

Big_O Complexidade Algoritmos EstruturasDeDados AnaliseDeDesempenho LeetCode

Complexidade temporal

• Diz respeito a quantos acesso você faz dentro de um array por exemplo

  • Isso quer dizer que se você percorre uma lista de informações uma única vez você tem um algoritmo que complexidade temporal de O(n)
  • Caso não tenha ficado claro, podemos pensar que caso percorremos mais uma vez essa lista teriamos um algoritmo com complexidade O(n * 2), mas normalmente os multiplos tentem as ser desconsiderados quando vamos analisar a complexidade do algoritmo
  • Ele é desconsiderado normalmente porque, como já comentamos é Big-O, busca encontrar o comportamento assintótico

  # O(n)
  def encontrar_maior(lista):
      maior = lista[0]
      for elemento in lista[1:]:
          if elemento > maior:
              maior = elemento
       return maior
   
  # O(n * 2) = O(n)
  def soma_e_maior(lista):
      soma = sum(lista)     # primeiro loop
      maior = max(lista)    # segundo loop
      return soma, maior

Complexidade espacial

• Diz respeito a quantidade de espaço que você ocupa dependendo do seu input

  • Por exemplo: caso você receba um input de uma lista com 10000 registros, o ultimo elemento, você consegue encontrar o ultimo elemento, você muito provavelmente vai resolve-lo, como uma solução que ocupa um espaço fixo, esse espaço fixo é representado por O(1)

  # O(1)
  def ultimo_elemento(lista):
      return lista[-1]
   
  # O(n)
  def copiar_lista(lista):
      copia = []
      for item in lista:
          copia.append(item)
      return copia

As complexidades mais comuns

• O(1) Resolução constante → Independente do INPUT teremos o espaço/tempo fixo Exemplo :

    def acessar_primeiro(lista):
        return lista[0]

• O(n) Resolução Linear → proporcionalmente ao tamanho do input. Exemplo :

 def encontrar_maior(lista):
        maior = lista[0]
        for elemento in lista[1:]:
            if elemento > maior:
                maior = elemento
         return maior
 

• O(n log n) Resolução Linearítma → Normalmente aparece no algoritmo ordenação como quicksort

        def busca_binaria(lista, alvo):
            inicio = 0
            fim = len(lista) - 1
 
            while inicio <= fim:
                meio = (inicio + fim) // 2
                if lista[meio] == alvo:
                    return meio
                elif lista[meio] < alvo:
                    inicio = meio + 1
                else:
                    fim = meio - 1
            return -1

Exemplo

# Importante lembrar que algortimos de ordenação possuem essa complexidade por baixo dos panos 
def ordenar(lista):
    return sorted(lista)    
        

• O(n²) – Resolução quadrática → Geralmente aparece quando temos loops aninhados percorrendo o input inteiro. O tempo cresce como n * n

 
def tem_duplicados_quadratico(lista):
    for i in range(len(lista)):
        for j in range(i + 1, len(lista)):
            if lista[i] == lista[j]:
                return True
    return False
 
 

• O(n!) – Resolução fatorial → Normalmente aparece em problemas que envolvem todas as permutações possíveis de um conjunto (força bruta em problemas de permutação, como alguns casos de backtracking, TSP ingênuo, etc.).

def permutacoes(lista):
    if len(lista) == 0:
        return [[]]
    if len(lista) == 1:
        return [lista[:]]
 
    resultado = []
    for i in range(len(lista)):
        elemento = lista[i]
        restante = lista[:i] + lista[i+1:]
        for p in permutacoes(restante):
            resultado.append([elemento] + p)
    return resultado

• Vejo que muita gente tem dificuldade de compreender o que matematicamente ocorre nessas ocasiões ps: principalmente na logaritma

• Vejo que a parte mais relevante para nosso contexto é visualizar como ela escala em comparação com as outras

• Falando especificamente da logartima é importante compreender que O(log n) faz com que ao dobrar nosso input, nosso gasto não dobramos o numero de operações, ou seja ele cresce de forma linear, no entanto com uma curva bem menos acentuada que a linear

Conclusão

• Big O descreve como tempo e espaço escalam com o tamanho do input, não a performance absoluta.
• Focar no comportamento assintótico ajuda a comparar abordagens, ignorando constantes e fatores menores.
• Escolher estruturas e algoritmos que mantenham O(log n) ou O(n) geralmente garante soluções práticas para a maioria dos casos.

Tópicos Relacionados

• Array - Estrutura com acesso O(1)
• Complexidade de Algoritmos - Análise de eficiência
• Introdução às Estruturas de Dados - Fundamentos

Veja também

• Notação Big O - Conteúdo em português do livro “Entendendo Algoritmos”