Notação Assimptótica e Teorema Mestre

Notação Assimptótica

A secção de IAED dos resumos sobre esta matéria já cobre os aspetos relevantes a abordar, ainda que relativamente superficialmente. Tentando relembrar estes conceitos de uma forma sucinta:

  • Majorante assimptótico:

    gO(f) sse cn0,nn0,g(n)cf(n)g \in O(f) \text{ sse } \exists_{c}\exists_{n_0}, \forall_{n \geq n_0}, \quad g(n) \leq c\cdot f(n)

    É o limite assimptótico superior, com notação OO - afere a complexidade no pior caso.

  • Minorante assimptótico:

    gΩ(f) sse cn0,nn0,g(n)cf(n)g \in \Omega(f) \text{ sse } \exists_{c}\exists_{n_0}, \forall_{n \geq n_0}, \quad g(n) \geq c\cdot f(n)

    É o limite assimptótico inferior, com notação Ω\Omega - afere a complexidade no melhor caso.

  • Tight-band:

    gΘ(f) sse c1,c2x0,nn0,c1f(n)g(n)c2f(n)g \in \Theta(f) \text{ sse } \exists_{c_1, c_2}\exists_{x_0}, \forall_{n \geq n_0}, \quad c_1\cdot f(n) \leq g(n) \leq c_2\cdot f(n)

    É o limite assimptótico apertado, com notação Θ\Theta - quando o melhor e o pior caso têm a mesma complexidade.

Houve ainda dois lemas associados à notação assimptótica abordados em aula, um deles diretamente relacionado com o limite acima:

Lema 1

gΘ(f) sse gO(f)gΩ(f).g \in \Theta(f) \text{ sse } g \in O(f) \wedge g \in \Omega(f).

Lema 2 - Transitividade

fO(g)gO(h)    fO(h).f \in O(g) \wedge g \in O(h) \implies f \in O(h).

As provas de ambos os lemas encontram-se nas notas do professor, no fim da página.


Muitas vezes, uma abordagem que permite diminuir significativamente o tempo assimptótico em que é possível resolver um problema é usar uma abordagem de Dividir e Conquistar.

Dividir para Conquistar

Metodologia:

  • Dividir o problema a resolver num conjunto de subproblemas.

  • Resolver (recursivamente) cada um dos subproblemas.

  • Combinar as soluções dos subproblemas para obter a solução do problema original.

Exemplos de problemas que têm soluções deste tipo são

  • Procura de um elemento numa array ordenada com Binary Search
  • Travessia de uma árvore binária
  • Ordenação de uma array com Merge Sort (pode ser útil rever, foi abordado em aula). As notas do professor abordam também a complexidade temporal de cada método do Merge Sort (e a sua complexidade total)

O Teorema Mestre oferece um método para calcular o crescimento assimptótico deste tipo de problemas.

Teorema Mestre

Teorema Mestre Simplificado

Sejam a1,b>1,d0a \geq 1, b > 1, d \geq 0 constantes e T(n)T(n) definido por

T(n)=aT(n/b)+O(nd)T(n) = a T(n/b) + O(n^d)

Diz então o Teorema Mestre Simplificado que

T(n)={O(nlogba)if d<logbaO(ndlogn)if d=logbaO(nd)if d>logbaT(n) = \begin{cases} O(n^{\log_b a}) && \text{if } d < \log_b a \\ O(n^d\log n) && \text{if } d = \log_b a \\ O(n^d) && \text{if } d > \log_b a \end{cases}

As constantes a,ba, b e dd devem ser pensadas da seguinte forma:

  • Nesta solução de D&C, cada problema de tamanho nn divide-se em a\mathbb{a} problemas de tamanho n/b\mathbb{n/b};
  • nd\mathbf{n^d} corresponde ao custo nesta solução para gerar os subproblemas, e, no fim, juntar os seus resultados (em relação a um problema de tamanho nn).

Prova

Pode ajudar a acompanhar esta prova desenhar no papel a árvore descrita na prova.

Na raiz, temos que o preço (pontual) é dado por O(nd)O(n^d).

Num segundo nível, temos aa subproblemas de tamanho n/bn/b. Portanto, cada um tem um custo de O(nbd)O(\frac{n}{b}^d). Consequentemente, no total, neste nível, a complexidade é aO(nbd)aO(\frac{n}{b}^d).

No terceiro nível, dividimos cada problema em aa subproblemas, obtendo então a2a^2 subproblemas. Cada um destes subproblemas terá dimensão n/b2n/b^2, pois dividimos cada problema no nível 2 bb vezes. Então, cada problema tem custo O(nb2d)O(\frac{n}{b^2}^d), pelo que a complexidade do nível todo é a2O(nb2d)a^2 O(\frac{n}{b^2}^d).

Fica então fácil de generalizar que no nível kk teremos aka^k problemas de tamanho nbk\frac{n}{b^k} com custo pontual O(nbkd)O(\frac{n}{b^k}^d).

Calcular a complexidade da nossa solução corresponde então a somar a complexidade de cada nível, até um nível da árvore em que o custo pontual é constante (neste caso assumimos que isso acontece apenas quando n=1n=1). Para isso precisamos de saber quantas divisões temos de fazer até chegar a esse nível. A resposta é o valor kk tal que nbk=1k=logbn\frac{n}{b^k} = 1 \Leftrightarrow k = \log_b n.

Ficamos então com o somatório:

k=0logbnO(ak(nbk)d)=O(ndk=0logbn(abd)k)\sum_{k=0}^{\log_b n} O \left( a^k \left(\frac{n}{b^k}\right)^d \right) = O \left( n^d \sum_{k=0}^{\log_b n} \left( \frac{a}{b^d} \right)^k \right)

Analisemos agora caso a caso:

  • No caso 1, temos que d<logbabd<aabd>1d < \log_b a \Leftrightarrow b^d < a \Leftrightarrow \frac{a}{b^d} > 1. Neste caso, o somatório explode e é dominado pelo último termo, ou seja a complexidade tem upper bound de
    O(nd(abd)logbn)=O(ndalogbnnd)=O(alogbn)O \left( n^d \left( \frac{a}{b^d} \right)^{\log_b n} \right) = O \left( n^d \frac{a^{\log_b n}}{n^d} \right) = O \left( a^{\log_b n} \right)
  • No caso 2, ficamos com O(nd(logbn+1))=O(ndlogn)O \left( n^d (log_b n + 1) \right) = O \left( n^d \log n \right)
  • No caso 3, o somatório é majorado por uma série que converge (uma vez que d>logbabd>aabd<1d > \log_b a \Leftrightarrow b^d > a \Leftrightarrow \frac{a}{b^d} < 1) pelo que O(nd)O \left( n^d \right)
Exemplo 1

Tenhamos T(n)=9T(n3)+nT(n) = 9T(\frac{n}{3}) + n. Aqui, podemos dizer que:

a=9,b=3,d=1a = 9, \quad b = 3, \quad d = 1

Daqui, obtemos que

logba=log39=2>1=d\log_{b}{a} = \log_{3}{9} = 2 > 1 = d

Assim sendo, admitimos que estamos na presença do caso 1, e que, portanto,

T(n)=O(nlogba)=O(n2).T(n) = O(n^{\log_{b}{a}}) = O(n^2).
Exemplo 2

Tenhamos:

int f(int n) {
  int i, j;
  i = 0;
  j = 0;
  while (i < n) {
    j++;
    i += 2;
  }
  if (n > 1) {
    i = 2*f(j) + f(j);
  }
  return i;
}

Podemos procurar ver como o ciclo se comporta (e qual é a sua condição de paragem) recorrendo ao método da tabela. Neste caso:

kk ii jj
00 00 00
11 22 11
22 44 22
... ... ...
kk 2k2k kk

Onde kk é a variável de controlo do loop (conta o número de iterações), e ii e jj são variáveis que vão sendo atualizadas durante o mesmo. Podemos notar que k=0k = 0 corresponde ao momento exatamente antes do loop.

Ora, podemos perceber que ii vai crescendo com aspeto 2k2k - isto é, vai sempre sendo igual ao dobro do número de iterações atual do ciclo. Além disso, através da tabela, podemos também observar que, no fim do ciclo, j=kj = k.

Temos que o ciclo para com ini \geq n - ou seja, quando

2knkn22k \geq n \leftrightarrow k \geq \frac{n}{2}

Podemos, então, dizer que o ciclo corre n2\frac{n}{2} vezes, e que a sua complexidade temporal é O(n)O(n).

Como observado, j=kj = k no fim do ciclo, pelo que a chamada recursiva da função (dentro do bloco if) é realizada com j=n2j = \frac{n}{2} duas vezes (a função recursiva é chamada duas vezes), pelo que podemos admitir que essa secção leva 2T(n2)2\cdot T(\frac{n}{2}). A função T(n)T(n) total da função corresponde, portanto, a

T(n)=2T(n2)+O(n).T(n) = \smartcolor{yellow}{2}\cdot T\left(\smartcolor{orange}{\frac{n}{2}}\right) + O(n).

Ora, daqui podemos retirar que

a=2,b=2,d=1logba=log22=1=da = 2, \quad b = 2, \quad d = 1 \\ \log_{b}{a} = \log_{2}{2} = 1 = d

Estamos na presença do caso 2, e portanto podemos admitir que

T(n)=O(ndlogn)=O(nlogn).T(n) = O(n^d \cdot \log{n}) = O(n \cdot \log{n}).
Exemplo 3

Tenhamos:

int f(int n) {
  int i = 0;
  while (i * i < n) {
    i++;
  }
  if (n > 1) {
    i = f(n / 4) + f(n / 4) + f(n / 4)
  }
  return i;
}

Mais uma vez vamos recorrer ao método da tabela para perceber como o loop se comporta:

kk ii
00 00
11 11
22 22
... ...
kk kk

ii cresce, portanto, de igual forma ao número de ciclos. Ao mesmo tempo, temos que a condição de paragem é

i2nk2nknkn12i^2 \geq n \leftrightarrow k^2 \geq n \leftrightarrow k \geq \sqrt{n} \leftrightarrow k \geq n^\frac{1}{2}

A complexidade do loop é, portanto, O(n)O(\sqrt{n}).

Além disso, a chamada recursiva dentro do bloco if é realizada três vezes, desta vez sem recorrer a "variáveis auxiliares" - a chamada é sempre feita com n4\frac{n}{4}. Temos, então, que

T(n)=3T(n4)+O(n)T(n) = 3 \cdot T(\frac{n}{4}) + O(\sqrt{n})

de onde obtemos

a=3,b=4,d=12logba=log43>12a = 3, \quad b = 4, \quad d = \frac{1}{2} \\ \log_{b}{a} = \log_{4}{3} > \frac{1}{2}

Estamos, portanto, na presença do caso 3, e portanto

T(n)=O(nlogba)=O(nlog43).T(n) = O(n^{log_{b}{a}}) = O(n^{log_{4}{3}}).
Exemplo 4

Tenhamos:

int f(int n) {
  int i = 0;
  int j = 0;
  while (n * n > i) {
    i += 2;
    j++;
  }
  if (n > 1) {
    i = 5 * f(n/2) + f(n/2) + f(n/2) + f(n/2)
  }
  while (j > 0) {
    i += 2;
    j--;
  }
  return i;
}

Neste caso temos dois loops, pelo que a complexidade de ambos será relevante para resolver o problema.

Fazendo a tabela para o primeiro loop:

kk ii jj
00 00 00
11 22 11
22 44 22
... ... ...
kk 2k2k kk

Temos que o primeiro loop para quando

in22kn2kn22,i \geq n^2 \leftrightarrow 2k \geq n^2 \leftrightarrow k \geq \frac{n^2}{2},

pelo que a sua complexidade será O(n22)=O(n2)O(\frac{n^2}{2}) = O(n^2).

Olhando já para o segundo loop (já voltamos ao if no meio), podemos observar que o número de iterações é exatamente o mesmo do primeiro - no primeiro, jj era igual ao número de iterações do mesmo. Aqui, decrescemos jj até chegar a 0: n22\frac{n^2}{2} iterações, tal como em cima. A complexidade será, claro O(n2)O(n^2). A soma das suas complexidades corresponderá a 2O(n2)2 \cdot O(n^2). Contudo, a constante 22 é irrelevante para o cálculo da complexidade, pelo que podemos só admitir que a complexidade conjunta dos ciclos será do tipo O(n2)O(n^2).

A chamada recursiva é realizada 4 vezes, dentro do if, sempre recorrendo a n2\frac{n}{2}, pelo que vamos ter

T(n)=4T(n2)+O(n2) a=4,b=2,d=2logba=log24=2=dT(n) = 4 \cdot T(\frac{n}{2}) + O(n^2)\\ \text{ } \\ a = 4, \quad b = 2, \quad d = 2\\ \log_{b}{a} = log_{2}{4} = 2 = d

pelo que estamos na presença do caso 2, e portanto

T(n)=O(n2logn).T(n) = O(n^2 \cdot \log{n}).

Existem mais alguns exemplos semelhantes nas notas do professor.

Teorema Mestre Generalizado

Este teorema pode ser estudado com mais detalhe aqui (incluindo a sua prova, bastante extensa).

Sejam a1,b>1a \geq 1, b > 1 constantes e T(n)T(n) definido por T(n)=aT(nb)+Θ(f(n))T(n) = aT(\frac{n}{b}) + \Theta(f(n))
Diz então o Teorema Mestre Generalizado que:

T(n)={Θ(nlogba)se f(n)O(nlogba)Θ(nlogbalogn)se f(n)Θ(nlogba)Θ(f(n))se f(n)Ω(nlogba)T(n) = \begin{cases} \Theta(n^{\log_b a}) && \text{se } f(n) \in O(n^{\log_b a}) \\ \Theta(n^{\log_b a}\log n) && \text{se } f(n) \in \Theta(n^{\log_b a}) \\ \Theta(f(n)) && \text{se } f(n) \in \Omega(n^{\log_b a}) \end{cases}

O primeiro caso precisa de uma condição de regularidade - pode ser encontrada nos slides e nas notas do professor, mas em ASA não é necessária.

Tal como no caso simples, devemos pensar nestas fórmulas da seguinte forma:

  • Nesta solução de D&C, cada problema de tamanho nn divide-se em a\mathbb{a} problemas de tamanho nb\mathbb{\frac{n}{b}};
  • f(n)\mathbf{f(n)} corresponde ao custo nesta solução para gerar os subproblemas, e, no fim, juntar os seus resultados (em relação a um problema de tamanho nn).

O segundo caso tem ainda mais uma generalização, que não vamos indicar aqui mas pode ser encontrada na Wikipedia.

Prova

O professor disse que a prova do teorema generalizado era muito complicada e que seria preciso bastante tempo para o explicar. A prova não foi dada em aula pelo que também não a vamos fazer aqui.
Pode no entanto ser encontrada no livro Introduction to Algorithms, incluído na bibliografia da cadeira.

Exemplo

Tenhamos:

int f(int n) {
  int i = 0;
  int j = n;

  if (n <= 1) return 1;

  while (j > 0) {
    i++;
    j /= 2;
  }

  for (int k = 0; k < 4; k++) {
    j += f(n/2);
  }

  while (i > 0) {
    j += 2;
    i--;
  }
  return j;
}

Neste exemplo estamos na presença de 3 loops. Em relação ao primeiro:

kk ii jj
00 00 nn
11 11 n2\frac{n}{2}
22 22 n4\frac{n}{4}
... ... ...
kk kk n2k\frac{n}{2^k}

Ora, temos que a condição de paragem é j == 1 (após isso acontece j == 0 e para), pelo que ocorrerão

n2k=1n=2kk=log2n\frac{n}{2^k} = 1 \leftrightarrow n = 2^k \leftrightarrow k = \log_{2}{n}

log2n\log_{2}{n} iterações, ou seja o loop tem complexidade O(logn)O(\log n).

O segundo loop corre em tempo constante (exatamente 4 vezes), e contém a chamada recursiva da função, que é chamada com n2\frac{n}{2}.

O terceiro loop corre também em tempo logarítmico (i=ki = kno final do primeiro loop, e neste estamos a decrementar ii 1 a 1 até chegar a 0).

Podemos, assim, dizer que

T(n)=4T(n2)+O(logn)T(n) = 4 \cdot T\left(\frac{n}{2}\right) + O(\log n)

Ora, aqui não podemos aplicar o Teorema Mestre simplificado (não temos algo do tipo O(nd)O(n^d), mas sim O(logn)O(\log n)). Teremos, então, de recorrer ao Teorema Mestre generalizado. Aqui, consideramos f(n)f(n) == logn\log n, e temos, claro, que

a=4,b=2,f(n)=logn nlogba=n2f(n)=lognO(n2),a = 4, \quad b = 2, \quad f(n) = \log n \\ \text{ } \\ n^{\log_{b}{a}} = n^2 \\ f(n) = \log n \in O(n^2),

pelo que estamos na presença do caso 1, e portanto

T(n)=Θ(n2).T(n) = \Theta(n^2).

Heaps e Heap Sort

Na terceira aula foram também abordados os conceitos de Heap e Heap Sort. Estes conteúdos já estão disponíveis na secção de resumos de IAED, pelo que não os abordaremos a fundo aqui. As notas do professor também explicam muito bem esta parte!

De qualquer maneira, para ter aqui algumas noções-chave:

Definição de Heap

Um array A[1,...,n]A[1, ..., n] diz-se um heap se:

1<in,A[parent(i)]A[i],\forall_{1 < i \leq n}, \quad A[\op{parent}(i)] \geq A[i],

com

parent(i)=i2left(i)=2iright(i)=2i+1\op{parent}(i) = \left\lfloor{\frac{i}{2}}\right\rfloor\\ \op{left}(i) = 2i\\ \op{right}(i) = 2i + 1
  • A função maxHeapify/fixDown assume que ambos os filhos do "nó" argumento são heaps.
  • A altura máxima de um heap com nn elementos é logn\log n.
  • Do ponto acima sai que podemos, no máximo, invocar recursivamente a função maxHeapify logn\log n vezes.
  • A construção de um heap é feita de baixo para cima, da direita para a esquerda.
  • O índice pelo qual queremos começar a construção, o índice do primeiro nó com filhos, é dado por n2\left\lfloor\frac{n}{2}\right\rfloor. A prova está nas notas do professor. Abaixo podemos encontrar 2 exemplos que ilustram esta proposição (aqui, ii é o índice do primeiro nó com filhos).

De realçar que aqui consideramos um array indexado a partir de 1 (e não 0), daí ii ser, respetivamente, 2 e 4, e não 1 e 3.

Priority queues

Priority queues, ou filas de prioridade em português, são estruturas de dados cuja implementação corresponde, tipicamente, a heaps - há, tal como max Heaps e min Heaps (sendo o heap ordenado de modo decrescente ou crescente, respetivamente), max Priority Queues e min Priority Queues (heaps ordenados pela sua prioridade, portanto). Funcionam como uma "fila de supermercado" - cada pessoa pode ter um valor de prioridade, e o seu lugar é ditado por essa ordem.

São normalmente implementados desta maneira por ser uma maneira particularmente eficiente de organizar este tipo de informação. O elemento com mais prioridade, por exemplo, pode ser obtido em tempo constante (O(1)O(1)), a operação de obter qualquer valor (consoante, claro, a sua prioridade) realizada em O(logn)O(\log{n}), e a inserção e remoção de elementos também.