Divisão e Conquista

Introdução sobre algoritmos de divisão e conquista¶

Resolvendo recorrências usando expansão de termos¶

Resolvendo recorrências usando árvores de recursão¶

Resolvendo recorrências usando indução matemática (método da substituição)¶

Resolvendo recorrências usando o Teorema Mestre¶

Usado para recorrências do tipo:

$T(n) = \begin{cases} aT(n/b) + f(n) & \text{ se não-trivial } \\ \Theta(1) & \text{ se trivial } \end{cases}$

O teorema consiste em comparar $f(n)$ com a grandeza $n^{\log_b a}$ e o que dominar assintoticamente é a solução da recorrência. A função $f(n)$ representa o custo associado às operações que são efetuadas dentro de uma única chamada recursiva, ignorando o custo adicional das outras chamadas recursivas (conquista). Por outro lado, $n^{\log_b a}$ representa o contrário, o custo associado às chamadas recursivas:

1. se $f(n) \prec n^{\log_b a}$: significa que o custo dominante da recorrência acontece nos filhos das (sub)árvores, isto é, o custo dos níveis da árvore de recursão vai progressivamente aumentando.

2. se $f(n) \equiv n^{\log_b a}$: significa que cada nível contribui igualmente para o custo.

3. se $f(n) \succ n^{\log_b a}$: significa que o custo dominante da recorrência se concentra nas raízes das (sub)árvores, isto é, o custo dos níveis da árvore de recursão vai progressivamente diminuindo.

Cada uma dessas situações descreve um caso do teorema, que acompanha condições necessárias e também a conclusão a ser tirada sobre a complexidade assintótica da recorrência em cada caso.

• Caso 1. Se $f(n) \in O(n^{\log_b(a) + \epsilon} )$ para $\epsilon > 0$, então $T(n) \in \Theta(n^{\log b a} )$

• Caso 2. Se $f(n) \in \Theta(n^{\log_b a})$, então $T(n) \in \Theta(n^{\log_b a} \log n)$

• Caso 3. Se $f(n) \in \Omega(n^{\log_b(a)-\epsilon})$ para $\epsilon > 0$ e atender uma condição de regularização $af(n/b) \leq cf(n)$ para $c > 0$ e a partir de $n \geq n_0$ , então $T(n) \in \Theta(f(n))$

Resolvendo recorrências usando o Akra-Bazzi¶

Se trata de uma generalização do teorema mestre, possibilitando a solução de recorrências do tipo:

$T(n) = \begin{cases} c_0 & n=x_0 \\ \sum_{i=1}^k a_iT(b_in) + f(n) & n > x_0 \end{cases}$

Onde: $c_0 \in \mathbb{R}, x_0 \in \mathbb{N},a_i>0,0<b_1<1$, $f(n)$ é uma função assintoticamente positiva. Além disso, seja $p$ a única raíz real da equação:

$\sum_{i=1}^k a_i b_i^p = 1$

O teorema de Akra-Bazzi conclui um limite assintótico justo para $T(n)$:

$T(n) \in \Theta(n^p + n^p \int_{n_0}^{n}\frac{f(x)}{x^{p+1}}dx)$

Estudo de caso: ordenação por intercalação (merge sort)¶

merge(left, right, a) // |left| = n ; |right| = m ; |a| = n + m
i = 1; j = 1; k = 1

while i <= n and j <= m
  if left[i] < right[j]
    a[k] = left[i]; i = i + 1
  else
    a[k] = right[j]; j = j + 1
  k = k + 1

while i <= n
  a[k] = left[i]; i = i + 1; k = k + 1

while j <= n
  a[k] = right[j]; j = j + 1; k = k + 1

merge-sort(a) // |a| = n
if n == 1 or n == 0 return
mid = floor(n / 2)
left = a[1 ... mid]
right = a[mid+1 ... n]
merge-sort(left)
merge-sort(right)
merge(left, right, a)

Estudo de caso: ordenação usando quick sort¶

particiona(a, l, r) // a indexado de l a r, inclusive
pivot = a[r]
i = l - 1
for j = 1 to r-1 
  if a[j] <= pivot 
    i = i + 1 
    swap(a, j, i) // troca elementos de posição
swap(a, i+1, r)
return i+1

Estudo de caso: subarranjo de soma máxima¶

O subarranjo de soma máxima pode estar: (1) na metade esquerda; (2) na metade direita; (3) cruzando o meio. Observe que, se estamos no caso (3), a restrição nos ajuda a encontrar o melhor subarranjo: a partir do meio, basta adicionarmos elementos à esquerda rastreando em que posição a soma fica máxima e o mesmo à direita. Assim, (1) e (2) são resolvidos diretamente pela recursão durante a conquista dos subproblemas e (3) é resolvido pelo procedimento max-sum-crossing-mid de complexidade linear $\Theta(n)$, onde n é o tamanho do arranjo.

max-sum-subarray(a, l, r) // a indexado de l a r, inclusive
if l == r return (l, r, a[l])
mid = floor((l + r)/2)
(l1, r1, s1) = max-sum-subarray(a, l, mid)
(l2, r2, s2) = max-sum-subarray(a, mid+1, r)
(l3, r3, s3) = max-sum-crossing-mid(a, l, r, mid)
if s1 > s2 and s1 > s3 return (l1, r1, s1)
else if s2 > s3 return (l2, r2, s2)
else return (l3, r3, s3)

max-sum-crossing-mid(a, l, r, mid) // a indexado de l a r, inclusive
s1 = −inf
s = 0
for i = mid down to l
  s = s + a[i]
  if s > s1
    s1 = s; l1 = i

s2 = −inf
s = 0
for i = mid+1 to r
  s = s + a[i]
  if s > s2
    s2 = s; r1 = i

return (l1 , r1 , s1 + s2 )

Estudo de caso: número de inversões em um arranjo¶

Estudo de caso: par de pontos mais próximos¶