Este apêndice faz uma rápida revisão dos conceitos de problema, instância, algoritmo, e consumo de tempo. Veja mais informações no sítio Análise de Algoritmos.
Todo problema computacional tem parâmetros. Quando especificamos os valores desses parâmetros, temos uma instância, ou exemplo, do problema.
Um algoritmo para um problema
deve receber os valores dos parâmetros
e devolver uma solução da correspondente instância
ou informar que a instância não tem solução.
(Essa exigência sobre o comportamento do algoritmo é deveras pesada,
pois obriga o algoritmo a tratar
não só das instâncias que aparecem em aplicações práticas
como também daquelas que nem parecem razoáveis
.)
Considere, por exemplo, o seguinte problema: Dados números inteiros $a$, $b$ e $c$, encontrar um número inteiro $x$ tal que $ax^2 + bx + c = 0$. Os parâmetros desse problema são $a$, $b$ e $c$. A tarefa de encontrar um número inteiro $x$ tal que $10x^2 + 20x + 30 = 0$ é uma instância do problema. Qualquer algoritmo para o problema deve receber os valores de $a$, $b$ e $c$ e devolver uma solução $x$ ou informar que a correspondente instância não tem solução.
[A propósito,
nosso conceito de algoritmo é muito mais amplo
que aquele difundido pela imprensa.
Para muitos jornalistas,
a ideia de algoritmo está restrita aos algoritmos de recomendação
das mídias sociais.
Esse é um tipo muito especial de algoritmo,
baseados em aprendizado de máquina e redes neurais.]
Para estimar o consumo de tempo de um algoritmo, precisamos adotar um modelo de computação. Adotaremos um modelo em que o consumo de tempo de cada operação aritmética entre dois números consome apenas $\Oh(1)$ unidades de tempo, ou seja, não depende do tamanho dos números. [Para problemas que precisam lidar com números muito grandes seria mais apropriado supor que a operação $a+b$, por exemplo, consome $\Oh(\log a + \log b)$ unidades de tempo.]
Suponha que um algoritmo $\Acal$ recebe um grafo $G$
e um vetor $c$ que atribui um número real a cada elemento
de $E(G)$.
A delimitação superior do consumo de tempo de $\Acal$ depende,
em geral,
não só das cardinalidades $n$ e $m$ de $V(G)$ e $E(G)$
como também do tamanho
de $c$,
que podemos representar pelo número
$\max\left( |c_{e}| : e\in E(G) \right)$
e indicar por $\,\omega$.
[Não confunda $\omega$
com $w$
.]
Dizemos que $\Acal$ é pseudopolinomial se consome $\Oh(n^p m^q\,\omega)$ unidades de tempo para algum $p$ em $\Zplus$ e algum $q$ em $\Zplus$.
Dizemos que $\Acal$ é polinomial se consome $\Oh(n^p m^q\,\log \omega)$ unidades de tempo. (Note que $\log \omega$ é, essencialmente, o número de dígitos decimais de $\omega$.)
Dizemos que $\Acal$ é fortemente polinomial se consome $\Oh(n^p m^q)$ unidades de tempo para algum $p$ em $\Zplus$ e algum $q$ em $\Zplus$. O consumo de tempo não depende de $c$ nesse caso.
Suponha que $T$ e $f$ são funções reais de uma variável inteira $n$.
Dizemos que $T$ é $\Oh(f)$
se existe uma constante $k$ e um número $n_0$
tais que $0 \leq T(n) \leq k f(n)$
para todo $n\geq n_0$.
Assim, a expressão $T$ é $\Oh(f)$
tem o sabor de $T \leq f$
.
Dizemos que $T$ é $\Omega(f)$
se existe uma constante $k$ e um número $n_0$
tais que $0 \leq k f(n) \leq T(n)$
para todo $n\geq n_0$.
Assim, a expressão $T$ é $\Omega(f)$
tem o sabor de $T \geq f$
.
Dizemos que $T$ é $\Theta(f)$
se $T$ é $\Oh(f)$ e $\Omega(f)$.
Portanto, a expressão $T$ é $\Theta(f)$
tem o sabor de $T = f$
.