Universidade Federal de Minas Gerais
Departamento de Ciência da Computação

CURSO DE PÓS-GRADUAÇÃO EM CIÊNCIA DA COMPUTAÇÃO PROJETO E ANÁLISE DE ALGORITMOS

Aluno: Eduardo Freire Nakamura
e-mail: nakamura@dcc.ufmg.br

1.

Avaliar as somas (0.5 + 0.5 + 0.5 + 0.5 pontos):

(a)

$\sum^{n}_{i=1}a^{i}$

$$S_{n}=\sum^{n}_{i=1}a^{i}$$

$S_{n}=a+a^{2}+a^{3}+a^{4}+\ldots+a^{n-1}+a^{n}$
$aS_{n}=a^{2}+a^{3}+a^{4}+a^{5}+\ldots+a^{n}+a^{n+1}$
aS_n-S_n=aⁿ⁺¹-a
S_n(a-1)=a(aⁿ-1)

$$S_{n}=a\frac{a^{n}-1}{a-1}$$

para a > 1,

S_n=n

para a = 1.

(b)

$\sum_{i=1}^{n}\frac{1}{i}$


A resolução deste somatório pode ser efetuada utilizando a aproximação por integral [CLR90], onde temos que:

$$\int_{m}^{n+1}f(x)dx\leq\sum_{i=m}^{n}f(i)\leq\int_{m-1}^{n}f(x)dx$$

assim,

 

$$\sum_{i=1}^{n}\frac{1}{i}\geq\int_{1}^{n+1}\frac{1}{x}dx=\ln(n+1)$$ (1)

e

 

$$\sum_{i=2}^{n}\frac{1}{i}\leq\int_{1}^{n}\frac{1}{x}dx=\ln(n)$$ (2)

De (1) e (2) obtemos

$$\ln(n+1)\leq\sum_{i=1}^{n}\frac{1}{i}\leq\ln(n)+1$$

ou seja,

$$\sum_{i=1}^{n}\frac{1}{i}=\ln(n)+O(1)$$

(c)

$\sum^{n}_{i=1}\log{i}$

$$S_{n}=\sum^{n}_{i=1}\log{i}$$

$S_{n}=\log{(1)}+\log{(2)}+\log{(3)}+\ldots+\log{(n)}$
$S_{n}=\log{(1\cdot 2\cdot 3\cdot\ldots\cdot n)}$

$$S_{n}=\log{(n!)}$$

Pela aproximação de Stirling [CLR90] pode-se escrever

$$\log{(n!)}=\Theta(n\log n)$$

(d)

$\sum^{n}_{i=1}\frac{1}{i(i+1)}$

$$S_{n}=\sum^{n}_{i=1}\frac{1}{i(i+1)}=\sum^{n}_{i=1}\left(\frac{1}{i}-\frac{1}{i+1}\right)$$

$$S_{n}=\left(1-\frac{1}{2}\right)+\left(\frac{1}{2}-\frac{1}{... ...frac{1}{4}\right)+\ldots+\left(\frac{1}{n-1}-\frac{1}{n}\right)$$

$$S_{n}=1-\frac{1}{n}$$

2.

Apresente a complexidade de tempo para os procedimentos abaixo (0.5 + 0.5 + 0.5 + 0.5 pontos):

(a)

 

        PROCEDURE FazAlgo ( n : integer);
        VAR i, j, k, x : integer;
        BEGIN
          x := 0;
          FOR i := 1 TO n - 1 DO
            FOR j := i + 1 TO n DO
              FOR k := 1 TO j DO x := x + 1;
        END;

Analisando o número de vezes que a variável x é incrementada, a um custo O(1), tem-se

$$T(n)=\sum_{i=1}^{n-1}\left(\sum_{j=i+1}^{n}\left(\sum_{k=1}^{j}1\right)\right)$$

$$T(n)=\sum_{i=1}^{n-1}\left(\sum_{j=i+1}^{n}j\right)$$

Fazendo

$$T'(n)=\sum_{j=i+1}^{n}j$$

$$T'(n)=(i+1)+(i+2)+(i+3)+\ldots+n$$

$$T'(n)=(n-i)\left[\frac{(i+1)+n}{2}\right]$$

$$T'(n)=\frac{n^{2}+n}{2} - \frac{i^{2}}{2} - \frac{i}{2}$$

então,

$$T(n)=\left(\frac{n^{2}+n}{2}\right) \left(\sum_{i=1}^{n-1}1\... ...1}^{n-1}i^2\right) - \frac{1}{2} \left(\sum_{i=1}^{n-1}i\right)$$

fazendo $\sum_{i=1}^{n-1}i^2 = \frac{(n-1)(n)[2(n-1)+1]}{6}$ [Knu73], tem-se

$$T(n)=\left(\frac{(n^{2}+n)}{2}(n-1)\right) - \frac{1}{2}\lef... ...+1]}{6}\right) - \frac{1}{2}\left(\frac{(n-1)(1+n-1)}{2}\right)$$

$$T(n)=\frac{n^{3}-n}{2} - \frac{2n^{3}-3n^{2}+n}{12} - \frac{n^{2}-n}{4}$$

$$T(n)=\frac{4n^{3}-4n}{12}$$

$$T(n)=\frac{n^{3}-n}{3}=O(n^{3})$$

(b)

 

         PROCEDURE Pesquisa ( n : integer);
         BEGIN
           IF n > 1
           THEN BEGIN
                Inspecione n*n*n elementos; // custo n^3
                Pesquisa (n/3);
                END;
         END;

Neste algoritmo é necessário analisar o número de inspeções feitas. Assim, considerando que a inspeção de um único elemento tem custo O(1), a seguinte relação de recorrência pode ser montada:

$$\begin{cases} T(1)=0 & \\ T(n)=n^{3}+T\left(n/3\right), & \text{para }n\gt 1 \end{cases}$$

$$T(n)=n^{3}+T\left(\frac{n}{3}\right)$$

$$T(n)=n^{3}+\frac{n^{3}}{3^3}+T\left(\frac{n}{3^{2}}\right)$$

$$T(n)=n^{3}+\frac{n^{3}}{3^3}+\frac{n^{3}}{3^6}+T\left(\frac{n}{3^{3}}\right)$$

$$T(n)=n^{3}+\frac{n^{3}}{3^3}+\frac{n^{3}}{3^6}+\frac{n^{3}}{3^9}+T\left(\frac{n}{3^{4}}\right)$$

$$T(n)=n^{3}\sum_{k=0}^{x-1}\left(\frac{1}{3^3}\right)^k+T\left(\frac{n}{3^{x}}\right)$$

Como T(1)=0, fazendo n=3^x tem-se $x=\log_{3}n$ então

$$T(n)=n^{3}\sum_{k=0}^{x-1}\left(3^{-3}\right)^k$$

$$T(n)=n^{3}\left[\frac{\left(3^{-3}\right)^{x}-1}{3^{-3}-1}\right]$$

$$T(n)=\frac{27n^{3}}{26}\left[1 - \left(3^{-3}\right)^{x}\right]$$

$$T(n)=\frac{27n^{3}}{26}\left[1 - \left(3^{x}\right)^{-3}\right]$$

$$T(n)=\frac{27n^{3}}{26}\left[1 - n^{-3}\right]$$

$$T(n)=\frac{27}{26}\left[n^{3} - 1\right]=O(n^{3})$$

(c)

 

        PROCEDURE Sort ( VAR A: ARRAY[1..n] OF integer;
                         i, j: integer );
        { n uma potencia de 2 }
        BEGIN
          IF i < j
          THEN BEGIN
               m := (i + j - 1)/2;
               Sort(A,i,m);        // custo = T(n/2)
               Sort(A,m+1,j);      // custo = T(n/2)
               Merge(A,i,m,j);     // custo = n-1 comparacoes no
                                   // pior caso
               { Merge intercala A[i..m] e A[m+1..j] em A[i..j] }
               END;
        END;

Para este algoritmo é importante observar o número de comparações feitas para ordenar o vetor. Observe que este algoritmo divide o vetor em duas partes, ordena e combina estas partes através do procedimento Merge que faz no pior caso n-1 comparações. Assim, a relação de recorrência para este algoritmo é:

$$\begin{cases} T(1)=0 & \\ T(n)=T\left(n/2\right)+ (n-1), & \text{para }n\gt 1 \end{cases}$$

$$T(n)=2T\left(\frac{n}{2}\right)+(n-1)$$

$$2T\left(\frac{n}{2}\right)=2^2T\left(\frac{n}{2^2}\right)+(n-2)$$

$$2^2T\left(\frac{n}{2^{2}}\right)=2^3T\left(\frac{n}{2^3}\right)+(n-2^2)$$

$$\vdots$$

$$2^{x-1}T\left(\frac{n}{2^{x-1}}\right)=2^xT\left(\frac{n}{2^x}\right)+(n-2^{x-1})$$

$$T(n)=\left(\sum_{k=0}^{x-1}n\right) - \left(\sum_{k=0}^{x-1} 2^{k}\right) + 2^xT\left(\frac{n}{2^x}\right)$$

$$T(n) = n(x) - \left( \frac{2^{x} - 1}{2 - 1}\right) + 2^xT\left(\frac{n}{2^x}\right)$$

Considerando que n é uma potência de 2, ou seja, n=2^x, tem-se que

$$T(n) = n\log_{2}(n) - \left( n - 1 \right)$$

$$T(n) = n\log_{2}(n) - n + 1 = O(n\log n)$$

(d)

 

      PROCEDURE Proc( n : integer );
      BEGIN
        IF n = 0 THEN RETURN 1
        ELSE RETURN Proc(n-1) + Proc(n-1)
      END;

Neste algoritmo a medida de tempo pode ser considerada como o número de vezes em que é feita a soma da recursão Proc(n-1) + Proc(n-1). Portanto, a relação de recorrência para este algoritmo é:

$$\begin{cases} T(0)=0 & \\ T(n)=2T(n-1) + 1, & \text{para }n\gt \end{cases}$$

T(n)=2T(n-1) + 2⁰

2T(n-1)=2²T(n-2) + 2¹

2²T(n-2)=2³T(n-3) + 2²

2³T(n-3)=2⁴T(n-4) + 2³

2⁴T(n-4)=2⁵T(n-5) + 2⁴

$$\vdots$$

2^n-1T(1)=2ⁿT(0) + 2^n-1

$$T(n)=2^{n}T(0) + \sum_{k=0}^{n-1}2^{k}$$

$$T(n)=\sum_{k=0}^{n-1}2^{k}$$

$$T(n)=\frac{2^{n} - 1}{2-1}$$

T(n)=2ⁿ - 1 = O(2ⁿ)

3.

Limite inferior: (1.5 + 1.5 pontos):
São dados 2n números distintos distribuídos em dois arranjos A e B, cada um com n elementos ordenados, tal que: $A[1]\gt A[2]\gt\ldots\gt A[n]$ e $B[1]\gt B[2]\gt\ldots\gt B[n]$. O problema é achar o n-ésimo maior número dentre estes 2n elementos.

(a)

Apresente um algoritmo ótimo para resolver esse problema. Implemente o seu algoritmo. A listagem da implementação deve ser entregue e o programa submetido.

Algoritmo

    Elemento nEsimoMaiorElementoR(Arranjo A,
                                  Arranjo B,
                                  Indice  inicioA,
                                  Indice  fimA,
                                  Indice  inicioB,
                                  Indice  fimB)
    {
 (1)   int tamanhoAB, pivoA, pivoB;

 (2)   tamanhoAB = fimA - inicioA + 1;

 (3)   pivoA =(tamanhoAB != 1)?(tamanhoAB/2 + inicioA - 1):inicioA;
 (4)   pivoB =(tamanhoAB != 1)?(tamanhoAB/2 + inicioB - 1):inicioB;

       /* A condicao de parada e quando restam dois ou menos
          elementos a serem comparados */
 (5)   if( tamanhoAB == 1 ) {
 (6)      return (A[pivoA] > B[pivoB]) ? A[pivoA] : B[pivoB];
 (7)   }

 (8)   if( A[pivoA] > B[pivoB] ) {
          /* Elimina os ganhadores de A e os perderores de B */
 (9)      fimB    -= pivoA - inicioA + 1;
(10)      inicioA = pivoA + 1;
(11)   } else {
           /* Elimina os ganhadores de B e os perderores de A */
(12)       fimA    -= pivoB - inicioB + 1;
(13)       inicioB = pivoB + 1;
(14)   }

       /* Aplica novamente o algoritmo na metade restante do
          problema */
(15)   return nEsimoMaiorElementoR(A,B,inicioA,fimA,inicioB,fimB);

    }

Análise de complexidade

Para a análise do custo será considerado o número de comparações entre os elementos de A e de B. Assim, pela linha (6) temos que T(1) = 1. Na linha (8) é feita uma única comparação e, nas linhas (9) e (10) metade dos elementos de A e B são descartados. A seguir, na linha (15) o algoritmo é aplicado novamente nas metades restantes de A e B de maneira que T(n) = 1 + T(n/2) para n>1. Desta forma a relação de recorrência para o algoritmo é

$$\begin{cases} T(1)=1 & \\ T(n)=T(n/2) + 1, & \text{para }n\gt 1 \end{cases}$$

$$T(n) = T\left(\frac{n}{2}\right) + 1$$

$$T\left(\frac{n}{2}\right) = T\left(\frac{n}{2^{2}}\right) + 1$$

$$T\left(\frac{n}{2^{2}}\right) = T\left(\frac{n}{2^{3}}\right) + 1$$

$$\vdots$$

$$T\left(\frac{n}{2^{x-1}}\right) = T\left(\frac{n}{2^{x}}\right) + 1$$

$$T(n) = T\left(\frac{n}{2^{x}}\right) + \sum_{k=1}^{x} 1$$

$$T(n) = T\left(\frac{n}{2^{x}}\right) + x$$

Assumindo que n é uma potência de 2, ou seja, n = 2^x (resultando em $x = \log_{2}n$), temos que

 

$$T(n) = 1 + \log_{2}(n) = O\left(\log(n)\right)$$ (3)

Descrição geral e decisões de projeto

Para facilitar a legibilidade e a análise da complexidade, o algoritmo foi escrito de forma recursiva. O ambiente de desenvolvimento e de testes utilizado foi uma estação UltraSparc da SUN com sistema operacional Unix. A linguagem de implementação foi o C utilizando o compilador gcc.

Com o objetivo de simplificar a implementação respeitando de forma fiel à especificação do problema (especificação da questão 3) os arranjos foram gerados com N+1 elementos sendo considerado apenas os elementos de índice 1 a N.

Descrição dos módulos

O programa implementado é constituído de dois módulos:

i.

rand - formado pelos arquivos rand.c (fornecido pelo professor) e rand.h. O arquivo rand.c possui a implementação das funções de geração de valores aleatórios enquanto o arquivo rand.h possui o cabeçalho destas funções.

ii.

nmaior - formado pelos arquivos nmaior.c e nmaior.h. O arquivo nmaior.c apresenta a implementação das funções relacionadas com o problema de encontrar o n-ésimo maior elemento. O arquivo nmaior.h disponibiliza o cabeçalhos das funções definidas em nmaior.c e a definição dos tipos de dados.

iii.

main - inclui o arquivo main.c com o programa principal.

O módulo rand é utilizado somente pelo módulo nmaior. O módulo principal (main) faz uso direto apenas do módulo nmaior.

Tipos de dados utilizados

No arquivo nmaior.h são definidos os seguintes tipos de dados e constantes:

• N - constante que define o tamanho dos elementos.
• Elemento - inteiro do tipo int. Define um elemento do Arranjo.
• Indice - inteiro do tipo int. Define o tipo usado para indexar os elementos dos Arranjos.
• Arranjo - vetor do tipo Elemento. Define um arranjo com N+1 elementos dos quais serão considerados apenas os elementos de índices i com $1\leq i \leq N$.

Descrição do formato de entrada

Os arranjos A e B são gerados automaticamente basta definir o valor da constante N no arquivo nmaior.h.

Descrição do formato de saída

A saída é textual seguindo o formato abaixo.

Arranjo A: 4065 2031 1011 499 245 113 51 21 5 1
Arranjo B: 6318 3158 1570 782 388 190 94 42 12 0
O 10o. maior elemento em O(lg(N)) eh: 245

Utilização do programa

Após compilado, basta executar a seguinte linha de comando: ``./main''.

Listagem de Testes

A seguir são listados alguns testes executados.

Arranjo A: 4065 2031 1011 499 245 113 51 21 5 1
Arranjo B: 6318 3158 1570 782 388 190 94 42 12 0
O 10o. maior elemento em O(lg(N)) eh: 245

Arranjo A: 100 95 90 85 80
Arranjo B: 10 9 8 7 5
O 5o. maior elemento em O(lg(N)) eh: 80

Arranjo A: 100 95 89 85
Arranjo B: 101 90 81 75
O 4o. maior elemento em O(lg(N)) eh: 90

Arranjo A: 87 8 7 5 1
Arranjo B: 777 654 92 89 75
O 5o. maior elemento em O(lg(N)) eh: 87

(b)

Prove que o seu algoritmo é ótimo, isto é, obtenha um limite inferior para o número de comparações para resolver esta classe de problemas.

  

Figura: Possíveis soluções para o problema da questão 3. Os elementos maiores do que o n-ésimo são, para este problema, irrelevantes (representados aqui pelo símbolo ``?''). Portanto, existem apenas 2n possíveis soluções.

Para encontrar o limite inferior para este problema podemos utilizar a árvore de decisão [CLR90].


Montagem da árvore de decisão


A árvore de decisão representa o número de comparações entre elementos de A e de B quando o algoritmo opera sobre uma entrada de tamanho n. Na árvore de decisão, cada nodo é denotado por (A[i]:B[j]) para algum $i \geq 1$ e $j\leq n$. Cada nó-folha da árvore representa uma das possíveis soluções (figura 1) com os n maiores elementos de A e B e são denotados por $<?;~?;~?;~\ldots; A[k]\gt$ ou $<?;~?;~?;~\ldots; B[k]\gt$ onde $1 \leq k \leq n$, A[k] ou B[k] é o n-ésimo maior elemento e ``?'' representam os elementos maiores do que ele. Assim, o total de nós-folhas é 2n. Como todos os elementos de A e B são distintos, nos interessa somente a comparação A[i]<B[j] ou A[i]>B[j]. A execução do algoritmo ótimo corresponde a um caminho qualquer do nó-raiz a um nó-folha. Em cada nodo a comparação A[i]<B[j] é feita. A sub-árvore da esquerda indica as possíveis comparações subseqüentes para A[i]<B[j]. A sub-árvore da direita indica as possíveis comparações subseqüentes para A[i]>B[j]. Note que montando a árvore de decisão desta maneira, ela é mínima, ou seja, não existe duas computações que possam levar a respostas equivalentes. Ou de maneira mais formal:


Sejam Alg o algoritmo usado para montar a árvore de decisão acima, S_i = Alg(A,B) a solução do algoritmo, C_i o caminho percorrido para encontrar S_i e n o tamanho de A e B. A árvore montada acima possui as seguintes características:

i.

$S_{i} \neq S_{j}$ para todo $i \neq j$ com $1 \leq i,j \leq 2n$ .

ii.

$C_{i} \neq C_{j}$ para todo $i \neq j$ com $1 \leq i,j \leq 2n$ .

iii.

Pelos ítens (i) e (ii), se S_i = Alg(A,B) e S_j = Alg(A,B), então i = j para todo $1 \leq i,j \leq 2n$.

iv.

Os ítens (i) e (ii) implicam que a árvore de decisão é mínima e Alg é ótimo.

Limite inferior para o pior caso


O comprimento do maior caminho do nó-raiz da árvore de decisão para seus nós-folhas representa o pior caso de número de comparações entre elementos de A e de B. Por conseqüência, o pior caso do algoritmo ótimo corresponde a altura h da sua árvore de decisão. A árvore de decisão montada, é uma árvore binária e, portanto, não possui mais de 2^h nós folhas. Como o número de nós-folhas da árvore é 2n podemos escrever

$$2n \leq 2^{h}$$ (4)

ou seja,

$$\begin{array} {ccl} h & \geq & \log_{2}2n \\ & \geq & \log... ...\ & \geq & 1 + \log_{2}n\\ & = & \Omega(\log n) \end{array}$$ (5)

Conforme o custo obtido em (3) o algoritmo apresentado no item (a) da questão 3 é ótimo.

4.

Árvore Binária de Pesquisa Sem Balanceamento (1 + 0,5 + 0,5 + 1 pontos)

Considere o algoritmo para pesquisar e inserir registros em uma árvore binária de pesquisa sem balanceamento. Devido à sua simplicidade e eficiência a árvore binária de pesquisa é considerada uma estrutura de dados muito útil. Considerando-se que a altura da árvore corresponde ao tamanho da pilha necessária para pesquisar na árvore é importante conhecer o seu valor. Assim sendo,

(a)

Determine empiricamente a altura esperada da árvore;


Metodologia utilizada

Para determinar a altura da árvore de forma empírica, foram utilizados valores de n (número de nós) tais que n = 2ⁱ com $1 \leq i \leq 20$. Para cada valor de n foram geradas 50 árvores randômicas calculando-se a altura média h_e(n) (tabela 1). Admitindo que a altura esperada é $h(n)\approx k_{0}\log_2 n$ foi calculado o valor de k₀ para cada n. Pelos valores de k₀ exibidos na tabela 1 e a curva da figura 5, percebemos que k₀ cresce com o valor n contudo, quanto maior o valor de n menor é o crescimento de k₀ sugerindo que quando n tende a infinito, o valor de k₀ é realmente constante. Assim, o valor de k₀ torna-se significativo quando n cresce, tendendo ao infinito. Para os valores simulados podemos calcular um k_0-medio da seguinte forma:

$$k_{0-medio} = \frac{1}{20} \sum_{i=1}^{20} k_{0}^{(i)}$$

onde k₀⁽ⁱ⁾ são os valores da tabela 1.

 

n h_e(n) h_b(n) h_v(n) k₀⁽ⁿ⁾

2 1 1 3 1,000

4 3 2 6 1,085

8 4 3 9 1,260

16 6 4 12 1,488

32 9 5 15 1,662

64 11 6 18 1,738

128 14 7 21 1,913

256 17 8 24 2,001

512 19 9 27 2,051

1024 21 10 30 2,095

2048 24 11 33 2,165

4096 27 12 36 2,193

8192 30 13 39 2,287

16392 33 14 42 2,294

32784 35 15 45 2,325

65536 38 16 48 2,364

131072 42 17 51 2,429

262144 44 18 54 2,428

524288 47 19 57 2,426

1048576 50 20 60 2,467

  

Figura: Gráfico da altura da árvore binária randômica sem balanceamento. A curva dos valores esperados foi desenhada utilizando a constante encontrada na literatura (k=2,988).

(b)

Mostre analiticamente o melhor caso e o pior caso para a altura da árvore;

Algoritmo de inserção

void Insere(Registro x, Apontador *p)
{
  if (*p == NULL) {
    *p = (Apontador) malloc(sizeof(Nodo));
    (*p)->Reg = x;
    (*p)->Esq = NULL;
    (*p)->Dir = NULL;
    return;
  }
  if (x.Chave < (*p)->Reg.Chave) {
    Insere(x, &(*p)->Esq);
    return;
  }
  if (x.Chave > (*p)->Reg.Chave)  Insere(x, &(*p)->Dir);
  else  printf(" Erro : Registro %d ja  existe na arvore\n", x.Chave);
}  /* Insere */

Pior caso

Analisando o algoritmo de inserção,o pior caso é quando os valores inseridos na árvore em ordem crescente ou decrescente resultando em uma lista linear, ou seja, h = n. Quando em ordem crescente, os elementos são inseridos sempre a esquerda da árvore. Quando em ordem decrescente, os elementos são inseridos sempre a direita da árvore. A figura 3 mostra um exemplo do pior caso da árvore binária randômica sem balanceamento.

  

Figura: Pior caso da árvore binária.

Melhor caso

Novamente recorrendo ao algoritmo de inserção, o melhor caso é quando os elementos são inseridos de forma que a árvore resultante seja balanceada, neste caso, a relação da altura com o número de nós é mostrada na tabela 2 de onde podemos concluir que n = 2^h+1-1, ou seja, $h = \log_2(n+1)-1$. A figura 4 mostra um exemplo do melhor caso quando a árvore fica balanceada.

  

Figura: Melhor caso da árvore binária.

 

h (altura) n (número de nós) 1

1 3

2 7

3 15

(c)

Compare os resultados obtidos no item (a) com resultados analíticos publicados na literatura.

Em [Dev86,Drm01,Drm02] é dito que quando n tende a infinito a altura esperada é $h(n)\approx 4.31107\ln n$ ou $h(n)\approx 2,98821\log_2 n$. Veja que os valores simulados sugerem um crescimento da constante proporcional ao valor de n, contudo, podemos observar que quanto maior o valor de n menor é o crescimento da constante k₀ de maneira que quando n tende a infinito, o valor de k₀ torna-se independente do valor de n. Assim, os valores obtidos em simulação são coerentes com o valor encontrado na literatura (figura 5). A figura 5 mostra o comportamento da constante (obtido em simulação) em relação ao valor 4.31107.

  

Figura: Comportamento da constante para os valores de n simulados, k₀ foi obtido pela simulação e k é o valor obtido na literatura.

(d)

Mostre analiticamente o número esperado de comparações para encontrar um registro existente na árvore (busca com sucesso).

Definições

Para demonstrar o número esperado de comparações da busca com sucesso serão necessárias algumas definições enunciadas em [Knu73].

Nó Interno (Internal Node). Um nó que não é raiz nem folha da árvore binária.

Nó Externo (External Node). Um nó folha da árvore binária.

Comprimento de Caminho Externo (External Path Length) doravante referenciado por $\mathbf{E}$. Constitui a soma de todos os caminhos do nó-folha de uma árvore binária para cada nó-externo.

Comprimento de Caminho Interno (Internal Path Length) doravante referenciado por $\mathbf{I}$. Constitui a soma de todos os caminhos do nó-folha de uma árvore binária para cada nó-interno.

A relação entre o Comprimento de Caminho Externo e o Comprimento de Caminho Interno de uma árvore binária é  

$$\mathbf{E}=\mathbf{I}+2n$$ (6)

onde n é o número de nós da árvore.

Considerando C_n o número médio de comparações em uma busca com sucesso e C_n' o número médio de comparações em uma busca sem sucesso.

Em uma busca por uma chave, assumindo que cada um dos n nós pode conter a chave procurada com a mesma probabilidade. Podemos definir:

 

$$C_{n} = 1 + \frac{\mathbf{I}}{n}$$ (7)

 

$$C_{n}' =\frac{\mathbf{E}}{n+1}$$ (8)

 

$$\mathbf{I} = C_{0}' + C_{1}' + \ldots + C_{n-1}'$$ (9)

Pelas e as equações (6), (7) e (8) obtemos

 

$$C_{n} = \left( 1 + \frac{1}{n} \right)C_{n}' - 1$$ (10)

Pelas equações (7) e (9) obtemos

 

$$C_{n} = 1 + \frac{C_{0}' + C_{1}' + \ldots + C_{n-1}'}{n}$$ (11)

Combinando (10) e (11)

 

$$(n + 1)C_{n}' = 2n + C_{0}' + C_{1}' + \ldots + C_{n-1}'$$ (12)

Subtraindo (12) por $nC_{n-1}' = 2(n-1) + C_{0}' + C_{1}' + \ldots + C_{n-2}'$ obtemos

 

$$C_{n}' = C_{n-1}' + \frac{2}{n+1}$$ (13)

Como C₀'=0 podemos facilmente chegar em

 

C_n' = 2H_n - 2 (14)

Substituindo (14) em (10) obtemos

 

$$C_{n} = 2\left( 1 + \frac{1}{n} \right)H_{n} - 3$$ (15)

onde H_n é o número harmônico. Pelo exercício 1, item (b), $H_{n} = \ln n + k$, então

$$C_{n} = 2\left( 1 + \frac{1}{n} \right)\left( \ln n + k \right) - 3$$

considerando n grande (tendendo a infinito), temos

$$C_{n} \approx 2\ln n$$

mudando o logaritmo para base 2

$$C_{n} \approx \frac{2\log_{2}n}{\log_{2}e} = 1.39\log_2 n$$

Bibliografia

CLR90

Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest.
Introduction to Algorithms.
MIT Press, June 1990.

Dev86

Luc Devroye.
A note on the height of binary search trees.
Journal of the ACM (JACM), 33(3):489-498, July 1986.

Drm01

Michael Drmota.
An analytic approach to the height of binary search trees.
Algorithmica, 29(1):89-119, 2001.

Drm02

Michael Drmota.
The variance of the height of binary search trees.
Theoretical Computer Science, 270(1-2):913-919, 2002.

Knu73

Donald E. Knuth.
Fundamental Algorithms, volume 1 of The Art of Computer Programming.
Addison-Wesley, Reading, Massachusetts, second edition, 1973.

About this document ...

This document was generated using the LaTeX2HTML translator Version 97.1 (release) (July 13th, 1997)

Copyright © 1993, 1994, 1995, 1996, 1997, Nikos Drakos, Computer Based Learning Unit, University of Leeds.

The command line arguments were:
latex2html -split 0 tp1.

The translation was initiated by Eduardo Freire Nakamura on 9/26/2002