Entendendo a notação Big O

Estruturas de Dados e Algoritmos em Python

Miriam Antona

Software Engineer

Notação Big O

  • Mede a complexidade no pior caso de um algoritmo
    • Complexidade de tempo: tempo total de execução
    • Complexidade de espaço: memória extra usada
  • Não usa segundos/bytes
    • Resultados variam conforme o hardware
  • Expressões matemáticas: $O(1)$, $O(n)$, $O(n^2)$...
Estruturas de Dados e Algoritmos em Python

Notação Big O

Uma representação gráfica de diferentes tipos de algoritmos na notação Big O.

Estruturas de Dados e Algoritmos em Python

$O(1)$

colors = ['green', 'yellow', 'blue', 'pink']

def constant(colors):
    print(colors[2])

constant(colors)

blue
Estruturas de Dados e Algoritmos em Python

$O(1)$

colors = ['green', 'yellow', 'blue', 'pink', 'black', 'white', 'purple', 'red']

def constant(colors):
    print(colors[2])  # O(1)

constant(colors)

blue
Estruturas de Dados e Algoritmos em Python

$O(n)$

colors = ['green', 'yellow', 'blue', 'pink']

def linear(colors):
  for color in colors:
    print(color)    

linear(colors)

green

yellow

blue

pink
Estruturas de Dados e Algoritmos em Python

$O(n)$

colors = ['green', 'yellow', 'blue', 'pink'] # n=4

def linear(colors):
  for color in colors:
    print(color)    # O(4)

linear(colors)
  • n=4: 4 operações
Estruturas de Dados e Algoritmos em Python

$O(n)$

colors = ['green', 'yellow', 'blue', 'pink', 'black', 'white', 'purple'] # n=7

def linear(colors):
  for color in colors:
    print(color)    # O(7)

linear(colors)
  • n=4: 4 operações
  • n=7: 7 operações
  • n=100: 100 operações
  • ...
  • complexidade $O(n)$
Estruturas de Dados e Algoritmos em Python

$O(n^2)$

colors = ['green', 'yellow', 'blue']

def quadratic(colors):  
  for first in colors:
      for second in colors:
          print(first, second)

quadratic(colors)
  • n=3: (3 x 3) 9 operações
  • n=100: (100 x 100) 10.000 operações
  • padrão quadrático
  • complexidade $O(n^2)$
green green
green yellow
green blue
yellow green
yellow yellow
yellow blue
blue green
blue yellow
blue blue
Estruturas de Dados e Algoritmos em Python

$O(n^3)$

colors = ['green', 'yellow', 'blue']

def cubic(colors):  
  for color1 in colors:
      for color2 in colors:
          for color3 in colors:
              print(color1, color2, color3)

cubic(colors)
  • n=3: (3 x 3 x 3) 27 operações
  • n=10: (10 x 10 x 10) 1.000 operações
  • padrão cúbico
  • complexidade $O(n^3)$
Estruturas de Dados e Algoritmos em Python

Calculando a notação Big O

colors = ['green', 'yellow', 'blue', 'pink', 'black', 'white', 'purple']
other_colors = ['orange', 'brown']

def complex_algorithm(colors):
  color_count = 0

  for color in colors:
      print(color)
      color_count += 1

  for other_color in other_colors:
      print(other_color)
      color_count += 1

  print(color_count)

complex_algorithm(colors)
Estruturas de Dados e Algoritmos em Python

Calculando a notação Big O

colors = ['green', 'yellow', 'blue', 'pink', 'black', 'white', 'purple']  # O(1)
other_colors = ['orange', 'brown']  # O(1)


def complex_algorithm(colors):
  color_count = 0          # O(1)


  for color in colors:
    print(color)           # O(n)
    color_count += 1       # O(n)


  for other_color in other_colors:
    print(other_color)     # O(m)
    color_count += 1       # O(m)


  print(color_count)       # O(1)


complex_algorithm(colors)  # O(4
Estruturas de Dados e Algoritmos em Python

Calculando a notação Big O

colors = ['green', 'yellow', 'blue', 'pink', 'black', 'white', 'purple']  # O(1)
other_colors = ['orange', 'brown']  # O(1)

def complex_algorithm(colors):
  color_count = 0          # O(1)

  for color in colors:
    print(color)           # O(n)
    color_count += 1       # O(n)

  for other_color in other_colors:
    print(other_color)     # O(m)
    color_count += 1       # O(m)

  print(color_count)       # O(1)

complex_algorithm(colors)  # O(4 + 2n
Estruturas de Dados e Algoritmos em Python

Calculando a notação Big O

colors = ['green', 'yellow', 'blue', 'pink', 'black', 'white', 'purple']  # O(1)
other_colors = ['orange', 'brown']  # O(1)

def complex_algorithm(colors):
  color_count = 0          # O(1)

  for color in colors:
    print(color)           # O(n)
    color_count += 1       # O(n)

  for other_color in other_colors:
    print(other_color)     # O(m)
    color_count += 1       # O(m)

  print(color_count)       # O(1)

complex_algorithm(colors)  # O(4 + 2n + 2m)
Estruturas de Dados e Algoritmos em Python

Simplificando a notação Big O

  1. Remova constantes
    • $O(4 + 2n + 2m)$ -> $O(n + m)$
  2. Variáveis diferentes para entradas diferentes
    • $O(n + m)$
  3. Remova termos menores
    • $O(n + n^2)$
Estruturas de Dados e Algoritmos em Python

Simplificando a notação Big O

  1. Remova constantes
    • $O(4 + 2n + 2m)$ -> $O(n + m)$
  2. Variáveis diferentes para entradas diferentes
    • $O(n + m)$
  3. Remova termos menores
    • $O(n + n^2)$ -> $O(n^2)$
Estruturas de Dados e Algoritmos em Python

Vamos praticar!

Estruturas de Dados e Algoritmos em Python

Preparing Video For Download...