bc1435 – Busca Binária e Merge-Sort, recorrências para o número de comparações

Veremos duas aplicações para solução assintótica de recorrência. Em cada uma delas, primeiro determinaremos o número máximo de comparações feitas entre elementos da entrada, onde máximo é tomado sobre todas as entradas com o mesmo número de itens, em seguida determinaremos a ordem de grandeza dessas funções que são o número de comparações em função do número de itens da entrada.

— Busca Binária, recorrência para o número de comparações —

Na Busca Binária é dado um vetor A de inteiros em ordem não-decrescente e um inteiro x e o algoritmo decide se x\in A. O algoritmo começa comparando x com a mediana de A e se não encontrou x continua, recursivamente, na primeira metade de A caso x seja menor que a mediana, ou na segunda metade caso x seja maior que a mediana. A mediana do vetor ordenado A indexado pelos naturais de i até f é o elemento do posição (i+f) \,\mathrm{div}\, 2 = \lfloor \frac{i+f}2 \rfloor.

Busca Binária:

 

Busca-Binaria

   Dado um vetor ordenado A[1..n] de inteiros e um inteiro x
   Devolve SIM se x ocorre em A e devolve NÃO caso contrário
   
   
 1  i <- 1;
 2  f <- n;
 3  achou <- NÃO;
 4  repita {
 5   	   m <- (i+f) div 2;
 6	   se (A[m] = x) então achou <- SIM;
 7           senao {
 8	     	   se (x < A[m]) então f <- m-1;
 9		     senao i <- m+1
10		   }
11	   }	   
12  até que (achou = sim ou f < i);
13  Devolve achou. 
   

 

Numa execução Busca Binária com A[1..n] quantas comparações entre elementos de A são realizadas? As comparações são feitas nas linhas 6 e 8 e o número de comparações depende dos elementos de A. Por exemplo, se o vetor tem 1 elemento então há dois casos: só a comparação da linha 6 é feita ou as duas são feitas. Adotaremos a visão pessimista de que sempre é feito o maior número de comparações, assim se n é par e a comparação da linha 6 falhou assumimos que o algoritmo continua na metade maior (no caso n ímpar tanto faz, as partes tem o mesmo tamanho). Desse modo, o número de comparações C(n) numa execução Busca Binária com A[1..n] é

\displaystyle C(n) = \begin{cases} 2 & \textrm{ se } n=1 \\ C\left(\lfloor n/2 \rfloor \right) + 2 & \textrm{ se } n > 1 \end{cases}

e sabemos que C(n) = \Theta (\log_2 n).

De fato, como fizemos para o caso do número de bits na representação de n, iteramos a recorrência e obtemos que C(n) = 2\lfloor \log_2 (n) \rfloor +2 é um chute para a solução. Agora vamos verificá-la usando indução: a base fica por conta do leitor. A hipótese de indução é que C(k) = 2\lfloor \log_2 (k) \rfloor +2  para todo inteiro k, 1 \leq k \leq n. Então

\displaystyle \begin{array}{rcl} C(n+1) &=& C \left( \left\lfloor \frac {n+1}2 \right\rfloor \right)+2 \\ &=& \left(2 \left\lfloor \log_2 \lfloor\frac{n+1}2 \rfloor \right\rfloor +2 \right)+2\\ &=& 2 \left\lfloor \log_2 \frac{n+1}2 \right\rfloor +2 +2\\ &=& 2 \left\lfloor \log_2 {(n+1)} -\log_2 2 \right\rfloor +2 +2\\ &=& 2 \left\lfloor \log_2 {(n+1)} - 1 \right\rfloor +2 +2\\ &=& 2 \left\lfloor \log_2 {(n+1)} \right\rfloor -2 +2 +2\\ &=& 2 \left\lfloor \log_2 {(n+1)} \right\rfloor +2 \end{array}

em que a terceira e a sexta igualdades são decorrência de alguma das propriedades de chão e teto. Portanto C(n) = 2\lfloor \log_2 (n) \rfloor +2 para todo n\geq 1.

 

— MergeSort, recorrência para o número de comparações —

O Merge-Sort é uma algoritmo que recebe um vetor A[1..n] de inteiros e rearranja os elementos de A em ordem não-decrescente. Começaremos com dois fatos que serão usados na resolução da recorrência do MergeSort.

Seja {b(n)} o número de dígitos na representação binária de {n}, para todo {n \geq 1}.

\displaystyle b(n) = \begin{cases} 1 & \textrm{ se } n=1 \\ b\left(\lfloor n/2 \rfloor \right) + 1 & \textrm{ se } n > 1 \end{cases}

Sabemos que {b(n) = \lfloor \log_2 (n) \rfloor +1}. Na soma

\displaystyle \sum_{i=1}^{n-1} b(i)

temos que todos os {n-1} contribui com ao menos 1 bit para a soma; todos, exceto o 1, contribui com um 2º bit para a soma; todos, exceto 1,2 e 3, contribui com 3 bits; todos a partir do 8 têm o quarto bit, e assim por diante, ou seja,

\displaystyle \sum_{i=1}^{n-1} b(i) = (n-1) + (n-2) + (n-4) + (n-8) +\cdots + (n-2^{b(n)-1})

e rearranjando os somandos a soma fica

n b(n) - (1+ 2 + 4 + 8 +\cdots + 2^{b(n)-1})

e a soma da P.G. de razão 2 é 2^{b(n)}-1. Com isso

\displaystyle \sum_{i=1}^{n-1} b(i) = n b(n) - 2^{b(n)}-1 =n(\lfloor \log n\rfloor +1) - (2^{\lfloor \log n\rfloor+1}-1)

Merge-Sort:

 

MergeSort(A,i,f)

   Dado um vetor A[i..f] de inteiros
   Devolve A com os elementos em ordem crescente.
   
   
 1 se (i-f > 0) então {
 2     m <- (i+f) div 2;
 3     MergeSort(i,m);
 4     MergeSort(m+1,f);
 5     para k de 1 até m-i+1 faça
 6        b[k] <- A[i+k-1];
 7     para l de m+1 até f faça
 8        c[l-m] <- A[l];
 9     k <- 1;
10     l <- 1;
11     b[m-i+2] <-  ∞;
12     c[f-m+1] <- ∞;
13     para r de i até f faça
14        se ( b[k] < c[l] ){A[r] <- b[k]; k <- k+1;}
15        senão {A[r] <- c[l]; l <- l+1;}
16    }
17 Devolve A.   

 

O número de comparações entre elementos do vetor A feitas por uma chamada de MergeSort(A,1,n), n>1, é o número de comparações feitas recursivamente nas chamadas das linhas 3 e 4 mais o número de compações feitas na linha 14 (n pois o resultado de cada comparação determina um elemento de A), logo

\displaystyle T(n) = \begin{cases} 0 & \textrm{ se } n=1\\ T\left( \left\lceil \frac n2 \right\rceil\right) + T\left( \left\lfloor \frac n2 \right\rfloor\right) + n & \textrm{ se } n>1 \end{cases}
e sabemos que T(n) = \Theta (n\log_2 n).

Entretanto, nesse caso é possível determinar uma solução exata. Para {n>1}, \displaystyle T(n+1) - T(n) =

\displaystyle T\left( \left\lceil \frac {n+1}2 \right\rceil \right) +T\left(\left\lfloor \frac {n+1}2 \right\rfloor \right) +(n+1) - T\left( \left\lceil \frac n2 \right\rceil \right) - T\left(\left\lfloor \frac n2 \right\rfloor \right) -n

e pelo Exercício 3 (aula sobre funções chão e teto) a equação acima resulta em

\displaystyle T(n+1) - T(n) = T\left( \left\lfloor \frac n2 \right\rfloor +1 \right) - T\left( \left\lfloor \frac n2 \right\rfloor \right) +1

e, para n=1, temos {T(2)-T(1) = T(2) = 2}. Tomando {D(n) = T(n+1)-T(n)} para todo {n\geq 1} temos

\displaystyle D(n) = \begin{cases} 2 & \textrm{ se } n=1 \\ D\left( \left\lfloor \frac n2 \right\rfloor\right) +1 &\textrm{ se } n>1 \end{cases}

cuja solução é \displaystyle D(n) = \left\lfloor \log_2 n \right\rfloor + 2

Exercício 1 Prove, usando indução, a afirmação acima.

Agora, (isso pode ser útil)

\displaystyle \begin{array}{rcl} \displaystyle T(n) &=& T(n) - T(1) \\ &=& \displaystyle\sum_{i=1}^{n-1} T(i+1) - T(i) \\ &=& \displaystyle\sum_{i=1}^{n-1} D(i) \\ &=& \displaystyle\sum_{i=1}^{n-1} \left\lfloor \log i \right\rfloor +2\\ &=&\displaystyle (n-1) + \sum_{i=1}^{n-1} \left\lfloor \log i \right\rfloor +1\\ &=&\displaystyle (n-1) + \sum_{i=1}^{n-1} b(i) \end{array}

e usando a solução para a somatória, que vimos acima, temos

\displaystyle \boxed{T(n) = n\left\lfloor \log n \right\rfloor + 2n - 2^{\lfloor \log n \rfloor +1}}

Deixe uma resposta

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s