Projeto e Análise de Algoritmos
1 $\ensuremath{º}$ Trabalho Prático

Tiago Alves Macambira

2003.1

1 Avaliar as Somas

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

Isso é simplesmente o somatório dos n primeiros elementos elementos de uma progressão geométrica, com $a_{1}=q=a$ . A dedução é trivial e encontra-se em qualquer livro de 2 $\ensuremath{º}$ grau. De qualquer forma, vamos a ela:

$S_{n}=a^{1}+a^{2}\ldots +a^{n}$

$S_{n}=a+aa\ldots +aa^{n-1}$

Introduzindo $a^{n+1}$ em ambos os lados

$S_{n}+a^{n+1}=a+aa^{1}+\ldots +aa^{n-1}+a^{n+1}=a+aa^{1}\ldots +aa^{n-1}+aa^{n}$

$S_{n}+aa^{n}=a+aa\ldots +aa^{n-1}+aa^{n}$

$S_{n}+aa^{n}=a+a\left( a+aa\ldots +aa^{n-1}\right)$

$S_{n}+aa^{n}=a+aS_{n}$

$S_{n}=\frac{a\left( a^{n}-1\right) }{a-1}$

Assim $\sum _{i=1}^{n}a^{i}=\frac{a\left( a^{n}-1\right) }{a-1}$ para $a\neq 1$ .

Para $a=1$ , $\sum _{i=1}^{n}a^{i}=1+\ldots +1=n$

1.2 $\sum _{i=1}^{n}\frac{1}{i}\protect$

Usando aproximação por integrais[1, p50]

A margem inferior:

$\begin{displaymath} \sum ^{n}_{k=m}\frac{1}{k}\geq \int _{m}^{n+1}\frac{dx}{x}=\ln \left( n+1\right) \end{displaymath}$

Para margem superior, derivamos a inequação:

$\begin{displaymath} \sum ^{n}_{k=2}\frac{1}{k}\leq \int _{1}^{n+1}\frac{dx}{x}=\ln n\end{displaymath}$

O que dá a margem:

$\begin{displaymath} \sum ^{n}_{k=1}\frac{1}{k}\leq \ln n+1\end{displaymath}$

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

$\begin{eqnarray*} \sum _{i=1}^{n}\log i & = & \log 1+\log 2+\ldots +\log n\\ &... ...og \left( 1\cdot 2\cdot \ldots \cdot n\right) \\ & = & \log n! \end{eqnarray*}$

Usando a ``Aproximação de Stirling''[1,3], chegamos em

$\begin{eqnarray*} \sum _{i=1}^{n}\log i & = & \log n!\\ & = & \Theta \left( n\log \right) \end{eqnarray*}$

2 Apresente a compliexidade de tempo para os procedimentos abaixo:

2.1 Pesquisa(n)

Caso Base:

$\begin{eqnarray*} T\left( 1\right) & = & 1\\ T\left( n\right) & = & 1+\left( n-... ...t( \frac{3}{5}n\right) \\ & = & n+T\left( \frac{3}{5}n\right) \end{eqnarray*}$

Aplicando o Master Theorem[1, p62], tendo que $a=1$ , $b=\frac{5}{3}$ e $f\left( n\right) =n$ , chegamos ao resultado que

$\begin{displaymath} T\left( n\right) =\Theta \left( f\left( n\right) \right) =\Theta \left( n\right) \end{displaymath}$

de qualquer forma, pelo método da substituição:

$\displaystyle T\left( n\right)$	$\textstyle =$	$\displaystyle n+T\left( \frac{3}{5}n\right)$	(1)
$\displaystyle T\left( \frac{3}{5}n\right)$	$\textstyle =$	$\displaystyle \frac{3}{5}n+T\left( \frac{3^{2}}{5^{2}}n\right)$	(2)
$\displaystyle T\left( \frac{3^{2}}{5^{2}}n\right)$	$\textstyle =$	$\displaystyle \frac{3}{5}n+T\left( \frac{3^{3}}{5^{3}}n\right)$	(3)
	$\textstyle \vdots$		(4)
$\displaystyle T\left( \left( \frac{3}{5}\right) ^{i}n\right)$	$\textstyle =$	$\displaystyle \left( \frac{3}{5}\right) ^{i}n+T\left( \left( \frac{3}{5}\right) ^{i+1}n\right)$	(5)
	$\textstyle \vdots$		(6)
$\displaystyle T\left( \left( \frac{3}{5}\right) ^{k}n\right)$	$\textstyle =$	$\displaystyle 1$	(7)

Ora, chegaremos ao fim da recursão quando

$\displaystyle \left( \frac{3}{5}\right) ^{k}n$	$\textstyle =$	$\displaystyle 1$	(8)
$\displaystyle k\log _{\frac{3}{5}}n$	$\textstyle =$	$\displaystyle 1$	(9)
$\displaystyle k$	$\textstyle =$	$\displaystyle \log _{\frac{5}{3}}n$	(10)

Logo,

$\displaystyle T\left( n\right)$	$\textstyle =$	$\displaystyle \left( \frac{3}{5}\right) ^{0}n+\left( \frac{3}{5}\right) ^{1}n+\ldots +\left( \frac{3}{5}\right) ^{k}n$	(11)
	$\textstyle =$	$\displaystyle \sum ^{k}_{i=0}\left( \frac{3}{5}\right) ^{i}n$	(12)
	$\textstyle =$	$\displaystyle \sum _{i=0}^{\log _{\frac{3}{5}}n}\left( \frac{3}{5}\right) ^{i}n$	(13)
	$\textstyle =$	$\displaystyle n\frac{1-\frac{3}{5}^{1+\log _{\frac{5}{3}}n}}{1-\frac{3}{5}}$	(14)

2.2 Fib

Vamos inicialmente ver a condição inicial dessa recursão

$\begin{eqnarray*} T\left( 0\right) & = & 1\\ T\left( 1\right) & = & 1 \end{eqnarray*}$

Para $n$ qualquer, a expressão de tempo desse algoritmo fica

$\begin{displaymath} T\left( n\right) =T\left( n-1\right) +T\left( n-2\right) \end{displaymath}$

Ora, a expressão acima é a função de recorrência que devolve o $n$ -ésimo numero de Fibonacci. Logo, a complexidade de tempo desse algoritmo será, para uma entrada $k$ , o valor do $k$ -ésimo número de Fibonacci, cujo valor é dado pela fórmula:

$\begin{displaymath} F_{n}=\frac{1}{\sqrt{5}}\left( \phi ^{n}-\hat{\phi }^{n}\right) \end{displaymath}$

Ou, arredondando para o inteiro mais próximo:

$\begin{eqnarray*} F_{n} & = & \left\lfloor \frac{\phi ^{n}}{\sqrt{5}}+\frac{1}{2}\right\rfloor \\ & = & \frac{\phi ^{n}}{\sqrt{5}} \end{eqnarray*}$

Onde $\phi =\frac{\left( 1+\sqrt{5}\right) }{2}$

A demonstração completa da obtenção de $F_{n}$ pode ser obtida em[3, p.212-219]

Finalmente, para fechar esse item, seria bom resaltar que $T\left( n\right) =O\left( 2^{n}\right)$

2.3 Sort1

O algoritmo é o merge-sort, que é $O\left( n\log n\right) .$ De qualquer forma, vamos à análise desse algoritmo.

2.3.1 Merge

Antes de prosseguirmos, precisamos saber a complexidade de tempo do procedimento MERGE. É sabido que dá para se construir sem muito esforço um algoritmo que fazer intercalação de dois vetores de tamanho iguais, cada um deles ordenados, em $O(n)$ . Para provar, propomos um algoritmo que faça isso e calcularemos a sua complexidade:

$\begin{algorithm} % latex2html id marker 203\par\caption{ Merge de dois vetore... ...r\STATE $A[x] \leftarrow AUX[x]$\par\ENDFOR \par\end{algorithmic}\end{algorithm}$
No algoritmo 1, acima o laco while mais externo garante que não haja sobreposição dos dois vetores que estão sendo. A cada iteração desse laço, os dois laços internos vão linearmente percorrendo e inserindo, ordenadamente, os elementos contidos nas respectivas partições de A que cada laço trata:

$\begin{displaymath} 3(m-i+1)+3[j-(m+1)+1]+(j-i+1)=4(j-i+1)=O(n)\end{displaymath}$

2.3.2 Sort1

Uma vez sabendo a complexidade de tempo do procedimento MERGE, sigamos para o cálculo da complexidade de tempo do algoritmo Sort1 como um todo.

$\begin{displaymath} T\left( n\right) =2T(n/2)+O(n)\end{displaymath}$

Aplicando o Master Theorem[1, p62], tendo que $a=2$ , $b=2$ e $f\left( n\right) =O\left( n\right)$ , chegamos ao resultado que

$\begin{displaymath} f\left( n\right) =\Theta \left( n^{\log _{b}a}\right) \Right... ...eft( n^{\log _{2}2}\log n\right) =\Theta \left( n\log n\right) \end{displaymath}$

Já temos uma idéia do que procurar. Desenvolvamos a equação recursiva por substituições:

$\begin{eqnarray*} T\left( n\right) & = & 2T(\frac{n}{2})+O(n)\\ & = & 4T\left(... ...t) & = & 2^{i}T\left( \frac{n}{2^{i}}\right) +iO\left( n\right) \end{eqnarray*}$

Fazendo $i=\lg n$

$\begin{eqnarray*} T\left( n\right) & = & n+O(n)\lg n\\ & = & o(n\lg n) \end{eqnarray*}$

2.4 Sort2

Esse algoritmo é muito parecido com o anterior.

A sua fórmula de recorrência é:

$\begin{displaymath} T\left( n\right) =\left\{ \begin{array}{c} 1,\\ 3T\left( \frac{n}{3}\right) +\frac{5n}{3}-2 \end{array}para\right. n=1\end{displaymath}$

Aplicando o Master Theorem[1, p62], tendo que $a=3$ , $b=3$ e $f\left( n\right) =\frac{5n}{3}-2$ , chegamos ao resultado que

$\begin{displaymath} f\left( n\right) =\Theta \left( n^{\log _{b}a}\right) \Right... ...eft( n^{\log _{3}3}\log n\right) =\Theta \left( n\log n\right) \end{displaymath}$

3 Limite Inferior

Ordenações através de comparações podem ser vistas abstratamente em termos de árvores de decisão.Uma arvore de decisão representa as comparações realizadas pelo algoritmo de ordenação quando ele trabalha em uma entrada de um dado tamanho.

O tamanho do caminho mais longo partindo da raíz de uma árvore de decisão para qualquer um de suas folhas representa o pior-caso no número de comparações que um algoritmo de ordenação realiza. Conseqüentemente, o pior-caso no número de comprarações para uma ordenação por comparação corresponde à altura da sua árvore de decisão.

Assim, achar o limite inferior para a altura de uma árvore de decisão equivale a achar o limite inferior para o tempo de execução de qualquer algoritmo de ordenação por comparação.

Considere a arvore de decisão de altua $h$ que ordena $n$ elementos. Como existem $n!$ permutações dos $n$ elementos, cada permutação representa uma ordem de ordenação distinta, a árvore tem que ter pelo menos $n!$ folhas. Já que uma árvore binária de altura $h$ tem não maus do que $2^{h}$ folhas, temos:

$\begin{displaymath} n!\leq 2^{h}\end{displaymath}$

que, através do uso de logaritmos, fica

$\begin{displaymath} h\geq \lg \left( n!\right) \end{displaymath}$

, já que a função é monotonicamente crescente. Usand as aproximação de Stirling, temos:

$\begin{displaymath} n!\geq \left( \frac{n}{e}\right) ^{n}\end{displaymath}$

onde $e$ é a base dos logaritmos naturais; assim:

$\begin{eqnarray*} h & \geq & \lg \left( \frac{n}{e}\right) ^{n}\\ & = & n\lg n-n\lg e\\ & = & \Omega \left( n\lg \right) \end{eqnarray*}$

[2,1]

4 Algoritmos de ordenação parcial: estudos comparativos

Em anexo, no documento estatisticas/tempo.txt, há um lista com os médios tempos de execução de vários algoritmos, para vários valores de n e k.

Também em anexo, gráficos relativos a essas estatisticas em graficos/time_graph_*.ps.

4.1 Experimentalmente, o número de comparações e movimentos-de-registro

Os algoritmos originados de algoritmos $O\left( n^{2}\right)$ perdem muito tempo fazendo comparações. O partital_Selection é destes aquele que mais realiza comparaçõe, seguido do insertion ( também originado de um algoritmo $O\left( n2\right) .$ Heap e quick sort realizam um número bem parecido de movimentações de regi:stros.

Em relação a comparação de registros, partial_insertion sort é o que mais se destaca quando do crescimento do n. Todos os outros ficam relativamente estáveis.

4.2 Tempo de Execução

4.2.1 Interpretação

É interessante notar que os algoritmos descendentes de algoritmos $O\left( n^{2}\right)$ , a exceção de $n$ muito pequenos, a medida que $k$ aumenta, sua performance diminui drasticamente. A perforamance desses algoritmos, contudo, ainda dá margens para interessantes surpresas: o partial_selection é disparadoo melhor algoritmo para $k=1$ . Mas também esse é o unico caso onde ele se dá bem. O partial_insertion_sort também apresenta uma acelerada taxa de crescimento com um aumento de $k$ . Ainda assim é, para valores de $k$ proximos de $\sqrt{n}$ uma boa opção, rivalizando nas faixas iniciais de $k$ até com o quicksort.

Enrtre os algoritmos cujos originais eram $O(n\log n)$ o quicksort é sempre a melhor opção. O partial_heapsort apresente, em alguns momentos, um custo inicial de montar a heap alto demais, em comparação com os algoritmos cujos originais são $O(n^{2})$ . Não pouca vezes perdeu para o insetion_sort com valores pequenos de k.

4.3 Resultados Analíticos

4.3.1 insertion sort

o que difere este algoritmo do original é que ele

Realiza um insertion sort normal para os k primeiros elementos ( $O(k^{2}$ ))
Para cada elemento fora desse intervalo, ele compara o valor destes com o do ultimo ( e maior ) elemento contudo no intervalo e, se for o caso, troca esses elementos de lugar, chamando novamente insertion sort nos k primeiros elementos para ordená-los ( $O(n-k)k^{2}$ )

A complexidade desse algoritmo fica então:

$\begin{eqnarray*} T(n) & = & O(nk^{2}+k^{2}-k^{3})\\ & & \end{eqnarray*}$

Logo, esse algoritmo, com L pequenos é bom, pois o fator $nk^{2}$ fica minimizado. Mas, aumentos em $k$ acarreta um crescimento muito grande na parcela $nk^{2}$

4.3.2 selection sort

O que difere esse do original é que o laço externo é limitado a rodar k vezes. Complexidade:

$\begin{eqnarray*} T\left( n\right) & = & \sum _{i=0}^{k-1}n-i\\ & = & k\frac{n... ... & = & \frac{2nk-k^{2}-k}{2}\\ & = & O\left( nk+k^{2}\right) \end{eqnarray*}$

Pela fórmula analítica fica fácil de ver pq o selection decresce tanto em relação ao insertion: apeser de ser inicialmente menor do que o insertions, k tem um grande peso nesse algoritmo.

4.3.3 heap_sort

Aqui nada de estranho: apenas u heap_invertido. AO final da ordenação dos k elementos , estes, que etavam em ordem reversa ao no final do vertor, são copiado de volta.

O custo para montar o heap é o mesmo: $O\left( n\right)$

O custo apra retirar os k primeiros: $k\cdot (\log$ m)

Total: $k(logm)$ :w

4.3.4 particion_quick

Melhor algoritmo para $k$ e $n$ grandes.

Bibliography

1: ``Introduction to Altorithms'', Cormen et al, 1st Edition
2: ``Algorithms, Data Structures, and Problem Solving With C++'' , Mark Allen Weiss.
3: ``Matemática Concreta - Fundantos para a Ciência da Computação'', Graham, Knuth, Patashnik; 2 $\ensuremath{ª}$ edição; LTC Editora

About this document ...

Projeto e Análise de Algoritmos
1 $\ensuremath{º}$ Trabalho Prático

This document was generated using the LaTeX2HTML translator Version 2K.1beta (1.48)

The command line arguments were:
latex2html -no_subdir -split 0 -show_section_numbers /tmp/lyx_tmpdir970vyiGPS/lyx_tmpbuf970nJ6gwv/novorel.tex

The translation was initiated by Tiago Macambira on 2003-05-23

Tiago Macambira 2003-05-23

Projeto e Análise de Algoritmos 1 Trabalho Prático

Projeto e Análise de Algoritmos
1 $\ensuremath{º}$ Trabalho Prático