Regras para Análise de Complexidade

De modo geral, podemos pensar na complexidade de um algoritmo como o somatório das complexidades de todos os fragmentos de código que o compõem. Portanto, precisamos saber como determinar a complexidade de blocos individuais de código e posteriormente combinar (somar) essas complexidades para obter o resultado desejado: a complexidade do algoritmo como um todo. A seguir mostramos exemplos de complexidades de trechos simples de código e ilustramos como usá-las no cálculo da complexidade de uma função.

Sentenças simples: Possuem complexidade constante, ou seja, $O(1)$.

# Sentenças simples
s = "Brasil"
i = 42
i += 1

Laços simples: Possuem complexidade linear no tamanho da entrada, ou seja, $O(n)$, em que $n$ é o tamanho da entrada.

# Laços simples
for i in range(n):
    # Sentenças simples

Laços aninhados: Possuem complexidade quadrática no tamanho da entrada, ou seja, $O(n^2)$, em que $n$ é o tamanho da entrada.

# Laços aninhados
for i in range(n):
    for j in range(n):
        # Sentenças simples

Exercícios

  • Qual é a complexidade da função abaixo?

def f(n, condicao):
    a = "Ordem e Progresso"
    if condicao:
      for i in range(n):
        # Sentenças simples
    else:
      for i in range(n):
        for j in range(n):
          # Sentenças simples
Clique para ver a solução

Temos que pensar no pior caso (quando o else é executado), portanto a complexidade é $O(n^2)$. Note que desconsideramos trechos com complexidade constante (atribuição de variável e condicionais) e termos de menor ordem (laço simples).

  • Qual é a complexidade do seguinte trecho de código?

a = 0
for i in range(n):
  for j in range(i + 1, n):
    a = a + i + j
print(a)
Clique para ver a solução

Conforme explicamos acima, temos um laço aninhado, cuja complexidade é $O(n^2)$.

  • Qual é a complexidade do seguinte trecho de código?

a = 0
for i in range(n):
  for j in range(n):
    for k in range(n):
      a = a + i + j + k
print(a)
Clique para ver a solução

No trecho de código acima, temos um laço aninhado, cuja complexidade é $O(n^3)$. Mas fique atento: nem todo laço aninhado possui complexidade polinomial (quadrática, cúbica, etc.).

Veja os exemplos abaixo.

i = n
while i > 1:
  i = i // 2
  print(i)

Perceba que a variável i é decrementada de forma diferente no laço acima. A cada iteração do while, o valor de i é dividido por dois. Assim, para n = 64, o trecho de código acima imprime 32, 16, 8, 4, 2, 1. O laço foi executado uma vez para cada um dos números impressos, ou seja, para n = 64, o laço executou 6 vezes. Se fizermos alguns testes executando o algoritmo com valores diferentes de n, veremos que o laço sempre executa $\log(n)$ vezes. Logaritmos são comuns em análise de complexidade, e é importante darmos atenção especial às aparições deles. Em geral, logaritmos aparecem sempre que estamos repetidamente dividindo coisas pela metade ou dobrando o tamanho de coisas.

  • Qual é a complexidade do seguinte trecho de código?

for i in range(n):
  i = 1
  while i < n:
    i = i * 2
    print(i)
Clique para ver a solução

Para cada uma das $n$ iterações do laço mais externo, o lado mais interno é executado $\log(n)$ vezes. Portanto, a complexidade do trecho de código acima é $O(n \times \log(n))$

  • Qual é a complexidade do seguinte trecho de código?

def eh_primo(n):
  limite = math.sqrt(n)
  for i in range(limite + 1):
    if n % i == 0:
      return False
  return True
Clique para ver a solução

Para cada uma das $\sqrt{n}$ iterações do laço acima, executamos uma quantidade constante de operações, logo a complexidade do trecho de código é $O(\sqrt{n})$.

  • Qual é a complexidade do seguinte trecho de código?

def fatorial(n):
  if n < 0:
    return -1
  elif n == 0:
    return 1
  else:
    return n * fatorial(n - 1)
Clique para ver a solução

Note que a função fatorial é chamada uma vez para cada valor no intervalo $[n, n - 1, n - 2, \dots, 0]$. Portanto, a complexidade do trecho é código acima é $O(n)$.

  • Qual é a complexidade do seguinte trecho de código?

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)
Clique para ver a solução

A função fib calcula, de forma extremamente ineficiente, o $n$-ésimo número da sequência de Fibonacci. Apesar de essa função possuir alguma semelhança em sua estrutura com a função fatorial, a complexidade da função fib é muito maior. Sua complexidade é $O(2^n)$. Isso ocorre porque são feitas muitas chamadas repetidas à função fib. Veja a ilustração abaixo e tente entender o que está acontecendo a cada chamada da função fib, que, por questões de espaço, escrevemos simplesmente como f. Mostramos o exemplo do cálculo de fib(5). Como você verá, a cada nível da árvore de chamadas abaixo, o número de chamadas à função f praticamente dobra.

Big-Oh

A título de curiosidade, existem formas mais eficientes de implementarmos a função fib, sem usar recursão, e sem fazer chamadas desnecessárias. Veja abaixo um exemplo:

def fib(n):
    if n <= 1:
        return n
    fib_n_menos_2 = 0
    fib_n_menos_1 = 1
    for i in range(2, n):
        fib_n = fib_n_menos_1 + fib_n_menos_2
        fib_n_menos_2 = fib_n_menos_1
        fib_n_menos_1 = fib_n
    return fib_n_menos_1 + fib_n_menos_2

A função acima calcula o $n$-ésimo termo da série de Fibonacci com complexidade $O(n)$.

Playground

# Use este espaço para praticar o que você aprendeu nesta seção. # Basta digitar o código no espaço abaixo e clicar 'run'.
Anterior Início Próximo