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:

  • Subpolinomial: a função de complexidade cresce mais lentamente que um polinômio. Exemplo: $f(n) = log(n)$. Um exemplo de algoritmo com complexidade logarítmica, e portanto subpolinomial, é a /cursos/algoritmos-python/pesquisa-ordenacao/pesquisa-binaria[pesquisa binária].

  • Polinomial: a função de complexidade é representada por um polinômio. Exemplos: $f(n) = O(n)$, $g(n) = O(n^2)$, $h(n) = O(n^3)$, e assim por diante. Um exemplo de algoritmo polinomial é o algoritmo de /cursos/algoritmos-python/pesquisa-ordenacao/insercao[ordenação por inserção].

  • Exponencial: a função de complexidade é representada por uma constante elevada a uma variável. Exemplo: $f(n) = O(2^n)$, em que $n$ é o tamanho da entrada do algoritmo. Um exemplo de algoritmo exponencial é o algoritmo para resolver o problema da Torre de Hanói.

  • Fatorial: a função de complexidade é uma função fatorial do tamanho da entrada do algoritmo. Exemplo: $f(n) = O(n!)$. Um exemplo de algoritmo fatorial é o algoritmo para gerar todas as permutações de um vetor de inteiros.

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

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

  • O que quer dizer a sentença: O algoritmo X é assintoticamente mais eficiente que o algoritmo Y?

Clique para ver a solução

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.

  • 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 $n$ é positivo.

# Laço a:
i = 0
while i < n:
  i += 1

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

# Laço c:
k = 0
while k < n:
  k *= 2
Clique para ver a solução

Dentre os laços acima, o laço "c" é o mais rápido, depois o laço "b", e depois o "a".

  • Ordene as funções abaixo em ordem crescente de complexidade assintótica.

    1. $f(n) = 2^n$.

    2. $g(n) = n^{3/2}$.

    3. $h(n) = n \log(n)$.

    4. $s(n) = n^{\log(n)}$.

Clique para ver a solução

A complexidade das funções segue a seguinte ordem: $h(n) < g(n) < s(n) < f(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