Problemas, instâncias, algoritmos e 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.

Problemas e suas instâncias

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:

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

Algoritmos para problemas

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

Consumo de tempo de um algoritmo

Efficiency is an ideological concept, not an economic concept.

— Noam Chomsky

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.  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.  O melhor caso corresponde às instâncias mais fáceis e o pior caso corresponde às instâncias mais difíceis do problema.

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.

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

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.

Exercícios

  1. Suponha que tenho um algoritmo para um certo problema que consome Ο(n²) unidades de tempo, sendo n o tamanho das instâncias.  Meu amigo diz ter um outro algoritmo para o mesmo problema que consome apenas Ω(n) unidades de tempo.  Devo ficar impressionado?
  2. [CLRS 3.1-3]  Explique por que a seguinte afirmação não faz sentido: o algoritmo A consome pelo menos Ο(n²) unidades de tempo.
  3. O seguinte algoritmo recebe um vetor P[1..n] com n ≥ 0 e devolve um vetor X[0..n].
    Algoritmo (P, n)
    1 _ para m crescendo de 0 até n faça
    2 ____ km
    3 ____ enquanto k ≥ 1 e Teste (P, k) = 0 faça
    4 _______ kk − 1
    5 ____ X[m] ← k
    6 _ devolva X

    Ao receber argumentos (Pn), 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.

Valid HTML 4.01 Strict Valid CSS!