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, .

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

Laços simples: Possuem complexidade linear no tamanho da entrada, ou seja, , em que é 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, , em que é o tamanho da entrada.

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


Exercícios

Exercício 1: 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

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


Exercício 2: 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)

Conforme explicamos acima, temos um laço aninhado, cuja complexidade é .


Exercício 3: 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)

No trecho de código acima, temos um laço aninhado, cuja complexidade é . 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 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.

Vejamos agora alguns exemplos mais complicados.


Exercício 4: Qual é a complexidade do seguinte trecho de código?

for i in range(n):
  i = 1
  while i < n:
    i = i * 2
    print(i)

Para cada uma das iterações do laço mais externo, o lado mais interno é executado vezes. Portanto, a complexidade do trecho de código acima é


Exercício 5: 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

Para cada uma das iterações do laço acima, executamos uma quantidade constante de operações, logo a complexidade do trecho de código é .


Exercício 6: 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)

Note que a função fatorial é chamada uma vez para cada valor no intervalo . Portanto, a complexidade do trecho é código acima é .


Exercício 7: Qual é a complexidade do seguinte trecho de código?

def fib(n):
  if n == 0:
    return 0
  if n == 1:
    return 1
  return fib(n - 1) + fib(n - 2)

A função fib calcula, de forma extremamente ineficiente, o -é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 é . 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.



Exemplo da execução da função fib(5).

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 == 0:
    return 0
  a = 0
  b = 1
  for i in range(2, n):
    c = a + b
    a = b
    b = c
  return a + b

A função acima calcula o -ésimo termo da série de Fibonacci com complexidade .