Análise de Algoritmos | Aulas | Dicionário | Índice

Problemas, instâncias, algoritmos, tempo

Esta página introduz o conceito de instância de um problema computacional e o conceito de tamanho de uma instância. Também discute, brevemente, a noção de consumo de tempo (ou desempenho, ou eficiência) de um algoritmo e as ideias de pior caso e melhor caso.

Uma das principais missões da análise de algoritmos é prever o consumo de tempo de algoritmos. Dado um algoritmo, procuramos estimar, a relação entre o consumo de tempo do algoritmo e o tamanho de sua entrada.

Problemas e suas instâncias

Todo problema computacional é uma coleção de casos particulares que chamaremos instâncias (= instances). Uma instância é especificada quando atribuímos valores aos parâmetros do problema. Em outras palavras, uma instância é especificada por um particular conjunto de dados do problema. [A palavra instância é um neologismo, importado do inglês. Ela está sendo empregada aqui no sentido de exemplo, exemplar, espécime, amostra, ilustração.]  Veja alguns exemplos:

• Problema da multiplicação de números naturais:  Dados números naturais u e v, encontrar a expansão decimal do produto u × v. (Veja mais na página Multiplicação de números.)

  Cada instância do problema é definida por dois números naturais. Por exemplo, os números 31415926535897932 e 14142135623730950488 definem uma instância.

• Problema da equação inteira do segundo grau:  Dados números inteiros a, b e c, encontrar um número inteiro x tal que ax² + bx + c = 0.

  Cada instância do problema é definida pelos valores de a, b e c. Por exemplo, os números 472, −311 e 57281 definem uma instância do problema; essa instância consiste em encontrar um número inteiro x tal que 472x² − 311x + 57281 = 0.

• Problema da ordenação de vetor inteiro:  Rearranjar (ou seja, permutar) os elementos de um vetor A[1 .. n] de números inteiros de modo que ele fique crescente. (Veja mais na página Ordenação por inserção.)

  Cada instância do problema é definida por um número natural n e um vetor A[1 .. n] de inteiros. Por exemplo, o número 5 e o vetor (876, 145, 323, 112, 221) definem uma instância do problema; essa instância consiste em rearranjar o vetor (876, 145, 323, 112, 221) em ordem crescente.

• Problema da subsequência crescente máxima:  Encontrar uma subsequência crescente de comprimento máximo de uma sequência (a₁, a₂, … , a_n) de números naturais. (Veja mais na página Subsequência crescente máxima.)

  Uma das instâncias do problema consiste em encontrar uma subsequência crescente máxima de (876, 145, 323, 112, 221).

• Problema do ciclo máximo num digrafo:  Encontrar um ciclo de comprimento máximo num digrafo.

  Cada instância do problema é especificada por um digrafo. Por exemplo, o digrafo com vértices  a, b, c, d  e arcos  ab, bc, cd, da, bd  especifica uma instância do problema.

Em geral, nem toda instância de um problema tem solução. Assim, por exemplo, a instância  (1, 2, 3)  do problema da equação inteira de segundo grau não tem solução, pois não existe um número inteiro x tal que 1x² + 2x + 3 = 0.

Em discussões informais é razoável confundir problema com instância e chamar tudo de problema. Mas em discussões mais técnicas é importante distinguir os dois conceitos.

Tamanho de uma instância

O tamanho (= size) de uma instância de um problema é a quantidade de dados necessária para descrever a instância (ou seja, o espaço de memória necessário para especificar os valores dos parâmetros que definem a instância). Em geral, o tamanho de uma instância é descrito por um único número natural, mas às vezes é mais conveniente usar dois ou mais números.

O conceito de tamanho está sendo apresentado de maneira propositalmente vaga para que possamos escolher, em cada caso, a definição mais apropriada.

• No problema da multiplicação de números naturais, por exemplo, parece razoável dizer que toda instância têm tamanho 2 (pois toda instância é especificada por dois números). Mas é mais apropriado dizer que o tamanho de uma instância é o número de caracteres necessário para especificar os dois números. Sob esta segunda definição, o tamanho da instância mencionada acima é 37.
• No problema da equação inteira do segundo grau, parece razoável dizer que todas as instâncias têm tamanho 3 (pois cada instância é especificada por três números). Dependendo das circunstâncias, entretanto, pode ser mais apropriado dizer que o tamanho de uma instância é o número de caracteres necessário para descrever a instância. Sob esta definição, o tamanho da instância (472, −311, 57281) é 12 (ou, quem sabe, 18).
• O tamanho de uma instância do problema de ordenação é n. Mas poderia também ser definido como o número total de caracteres necessário para escrever os valores dos elementos de A[1 .. n].
• O tamanho de uma instância do problema do ciclo máximo é n + m, sendo n o número de vértices e m o número de arcos do digrafo. Poderiamos também dizer que o tamanho da instância é o par (n, m).

Algoritmos para problemas

A solução de uma instância de um dado problema pode ser um número, um vetor, um valor booleano, etc., dependendo da natureza do problema. Já a solução de um problema é sempre um algoritmo.

Dizemos que um algoritmo resolve um dado problema se, ao receber a descrição de qualquer instância do problema, devolve uma solução da instância ou informa que a instância não tem solução. Essa exigência é deveras pesada, pois obriga o algoritmo a resolver não só as instâncias que aparecem em aplicações práticas como também aquelas instâncias patológicas que nem parecem razoáveis.

Desempenho de um algoritmo

Não confunda consumo de tempo com tempo de consumo!

— um aluno

Suponha que A é um algoritmo para um certo problema. Seja  t(I)  a quantidade de tempo que A consome para processar uma instância I do problema. Queremos estudar o comportamento de t em função do tamanho das instâncias. É preciso lembrar que, via de regra, um problema tem muitas instâncias diferentes de um mesmo tamanho e A consome um tempo diferente para cada uma. Para cada n, sejam

T_*(n)  e  T^*(n)

o mínimo e o máximo, respectivamente, de t(I) para todas as instâncias I que têm tamanho n. Assim, T_*(n) ≤ t(I) ≤ T^*(n) para toda instância I de tamanho n. Diremos que as funções  T_*  e  T^*  medem o consumo de tempo do algoritmo A no melhor caso (= best case) e no pior caso (= worst case), respectivamente. O melhor caso corresponde às instâncias mais fáceis e o pior caso corresponde às instâncias mais difíceis.

Por exemplo, o consumo de tempo do algoritmo pode ser  200n  no melhor caso e  3n²  no pior caso. (Como se faz usualmente, estamos ignorando os valores pequenos de n, para os quais 200n é maior que 3n².)

Em geral, o consumo de tempo é proporcional ao número operações elementares que o algoritmo executa ao processar a instância. Tipicamente, uma operação elementar é uma operação aritmética entre variáveis do algoritmo, ou uma comparação entre duas variáveis, ou uma atribuição de valor a uma variável. Não é necessário contar todas as operações elementares: basta escolher uma operação específica de modo o consumo de tempo do algoritmo seja proporcional ao número de execuções dessa operação. No problema da ordenação, por exemplo, parece óbvio que a operação relevante é a comparação entre elementos do vetor. Já no problema da equação inteira do segundo grau, parece claro que todas as operações aritméticas que envolvem a, b e c são relevantes.

Consumo de tempo assintótico

Algorithm analysis usually means give a big-O figure for the running time of an algorithm. (Of course, a big-Theta bound is even better.)

— Ian Parberry, Problems on Algorithms

We want a statement about software, not hardware.

Suponha que A é um algoritmo para um problema P. Em termos de minutos e segundos, a quantidade de tempo que A consome para processar uma dada instância de P depende da máquina usada para executar A. Mas essa dependência se resume a uma constante multiplicativa: se A consome tempo t numa determinada máquina, consumirá tempo 2t numa máquina duas vezes mais lenta e t/2 numa máquina duas vezes mais rápida. Para eliminar a dependência da máquina, basta discutir o consumo de tempo de A a menos de constantes multiplicativas. A notação assintótica (Ο, Ω, Θ) é ideal para fazer isso.

Suponha que T^* e T_* são as funções que medem, em termos do tamanho das instâncias, o consumo de tempo de A no pior e no melhor caso, respectivamente.

• Se T^*(n) está em Ο(n²), por exemplo, dizemos que A consome Ο(n²) unidades de tempo no pior caso. Como Ο( ) tem sabor de ≤, a frase no pior caso é redundante pois T_*(n) também estará em Ο(n²). Portanto, devemos dizer, simplesmente, que A consome Ο(n²) unidades de tempo.
• Se T^*(n) está em Ω(n²) dizemos que A consome Ω(n²) unidades de tempo no pior caso. Como Ω( ) tem sabor de ≥, a frase no pior caso não é redundante.

Se T^*(n) está em Ο(n²) e em Ω(n²), e portanto em Θ(n²), podemos dizer que A consome tempo proporcional a n² no pior caso, embora isso constitua um abuso do significado usual de proporcional.

• Se T_*(n) está em Ω(n), por exemplo, dizemos que A consome Ω(n) unidades de tempo no melhor caso. A frase no melhor caso é redundante: devemos dizer, simplesmente, que A consome Ω(n) unidades de tempo.
• Se T_*(n) está em Ο(n), dizemos que A consome Ο(n) unidades de tempo no melhor caso. Desta vez, a frase no melhor caso não é redundante.