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 de um algoritmo e as ideias de "pior caso" e "melhor caso".
Todo problema computacional é uma coleção de "casos particulares" que chamaremos instâncias. [A palavra instância é um (mau) neologismo, importado do inglês. Ela está sendo empregada aqui no sentido de exemplo, exemplar, espécime, amostra, ilustração.] Cada instância é definida por um conjunto de dados. Eis alguns exemplos:
Cada instância do problema é definida por dois números naturais. Por exemplo, os números 3141592653589793238462643383 e 1414213562373095048801688724209 definem uma instância.
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. A instância consiste em encontrar um número inteiro x tal que 472x² − 311x + 57281 = 0.
Cada instância do problema é definida por um número natural n e um vetor A[1…n]. Por exemplo, o número 5 e o vetor (876, 145, 323, 112, 221) definem uma instância do problema. A instância consiste em rearranjar o vetor (876, 145, 323, 112, 221) em ordem crescente.
Uma das instâncias do problema consiste em encontrar uma subsequência crescente máxima de (876, 145, 323, 112, 221).
Cada instância do problema é definida por um digrafo. Por exemplo, o digrafo com vértices x, y, w, z e arcos xy, yw, wz, zx, yz define uma instância do problema.
Uma das instâncias do problema consiste em encontrar um ciclo de comprimento pelo menos 5 no digrafo que tem vértices a, b, c, d, e e arcos ad, ea, db, be, dc, ce.
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.
O tamanho de uma instância de um problema é a quantidade de dados necessária para descrever a instância (ou seja, o "espaço" necessário para especificar a instância). Em geral, o tamanho de uma instância é descrito por um único número natural, mas às vezes é mais conveniente usar um par, ou até um terno, de números naturais.
O conceito de tamanho está sendo apresentado de maneira propositalmente vaga para que possamos escolher, em cada caso, a definição mais apropriada.
Dizemos que um algoritmo resolve um 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).
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 a relação entre t(I) e o tamanho das instâncias. 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 e no pior caso, respectivamente.
Por exemplo, o consumo de tempo do algoritmo pode ser 200n no melhor caso e n² no pior caso. (Como se faz usualmente, estamos ignorando os valores pequenos de n para os quais 200n é maior que n².)
Às vezes, convém medir o consumo de tempo pelo número de operações elementares que o algoritmo executa ao processar a instância. Aqui, uma operação elementar é uma operação aritmética (soma, subtração, multiplicação, divisão) entre dois números inteiros, ou uma comparação entre dois inteiros, ou uma atribuição de valor a uma variável simples. Não é necessário contar todas as operações elementares: basta contar as mais relevantes. É claro que a ideia de "relevante" varia de problema para problema: no problema da ordenação, a operação mais relevante é a comparação, enquanto no problema da equação inteira do segundo grau as operações aritméticas são as mais relevantes.
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
Seja 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 o efeito da máquina 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 o efeito 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.
Sejam, pois, T∗ e T∗ as funções que medem o consumo de tempo de A no pior e no melhor caso, respectivamente, em termos do tamanho das instâncias.
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".
| Algoritmo (P, n) |
| 1 _ para m crescendo de 0 até n faça |
| 2 ____ k ← m |
| 3 ____ enquanto k ≥ 1 e Teste (P, k) = 0 faça |
| 4 _______ k ← k − 1 |
| 5 ____ X[m] ← k |
| 6 _ devolva X |
Ao receber argumentos (P, n), a função Teste devolve 1 ou 0 e consome Ο(n) unidades de tempo para dar a resposta. Calcule detalhadamente o consumo de tempo do Algoritmo no pior e no melhor casos.