Modelo de Custos

Na prática, desejamos criar algoritmos cujas funções de complexidade cresçam o mais lentamente possível. Ao comparar dois algoritmos, o algoritmo mais eficiente (mais rápido) será aquele cuja função de complexidade cresce mais lentamente. De modo geral, o tempo de execução de um algoritmo é proporcional ao tamanho de sua entrada. Isto é, se um algoritmo opera sobre uma lista de elementos, quão maior for a lista, mais demorada será sua execução. Por isso, dados dois algoritmos com complexidades diferentes, dizemos que o melhor deles é aquele cuja função de complexidade cresce mais lentamente à medida em que aumentamos o tamanho da entrada.

Diferentes algoritmos podem possuir diferentes complexidades assintóticas. As complexidades mais comuns são:

O gráfico abaixo ilustra alguns destes tipos de complexidade assintótica e quão rapidamente elas crescem com o tamanho da entrada:


Modelo de custos para análise de algoritmos.

O gráfico acima (no qual o eixo y representa o tempo de execução dos algoritmos e o eixo x representa o tamanho da entrada) nos ensina um princípio importante: se projetarmos algoritmos eficientes (lineares ou logarítmicos, por exemplo), conseguiremos processar entradas de tamanhos muito grandes, ao passo que se nosso algoritmo para um determinado problema for exponencial ou fatorial, conseguiremos resolver problemas de tamanhos muito pequenos em tempo hábil.


Exercícios

Exercício 1: O que quer dizer a sentença: O algoritmo X é assintoticamente mais eficiente que o algoritmo Y?

Dizer que o algoritmo X é assintoticamente mais eficiente que o algoritmo Y significa que o algoritmo X será sempre uma escolha melhor para entradas muito grandes.


Exercício 2: Ordene os laços abaixo do mais eficiente (o que executa mais rapidamente) para o menos eficiente (executa mais lentamente), assumindo que o valor de é positivo.

# Laço a:
i = 0
while i < n:
  i++
 
# Laço b:
j = 0
while j < n:
  j += 2

# Laço c:
k = 0
while k < n:
  k *= 2

Dentre os laços acima, o laço c é o mais rápido.


Exercício 3: Ordene as funções abaixo em ordem crescente de complexidade assintótica.

  1. .
  2. .
  3. .
  4. .

A complexidade das funções segue a seguinte ordem: .