ANÁLISE E COMPLEXIDADE DE ALGORITMOS

Prévia do material em texto

INSTITUTO FEDERAL DO ESPÍRITO SANTO – CAMPUS SERRA 
 
 
BACHARELADO EM SISTEMA DE INFORMAÇÃO 
 
 
 
JOHNSON SUDRE 
JEAN CARLOS PENAS 
 
TÉCNICAS DE ANÁLISE E COMPLEXIDADE DE 
ALGORÍTMOS 
 
 
 
 
 
 
 
 
 
 
SERRA 
2013 
 2 
JOHNSON SUDRE 
JEAN CARLOS PENAS 
 
 
 
 
TÉCNICAS DE ANÁLISE E COMPLEXIDADE DE 
ALGORÍTMOS 
 
 
 
 
Tr ab a l ho ap r e s en tad o à d i s c ip l in a 
E s t r u tu r a D e Dad os do cu r so 
B ach a r e l ado em S i s t em a d e 
In f o r m ação do In s t i t u to Fed e r a l do 
E s p í r i t o S an to – Cam pu s S e r r a , pa r a 
av a l i a ção p a r c i a l . 
P ro f e s so r a : M ar t a Ta l i t h a 
 
 
 
 
 
SERRA 
2013 
 
 
 
 
 3 
 
 
Apresentação 
 
E s t e é um t r ab a lho e l ab or ado p e l a p r o f es s o r a M ar t a Ta l i t h a , n a 
d i s c i p l i n a d e e s t ru t u ra de dado s com o t em a t é cn i ca s de an á l i s e e 
co mpl ex i d ad e d e a lg o r i t mo s , n es t e r e l a t ó r io s e r á ab o rd ado co n ce i tos 
d e com o s e l ec i on a r a l go r i t mo s q u e r es o l v em o mesm o p r o b l em a em 
f u n ção da su a e f i c i ên c i a e t am bém vam os an a l i s a r a com pl ex id ad e 
d os a l go r i tm os q ue e s t á as so c i ad a ao cus t o . Es s es co nce i t os s e r ão 
ap l i c ad os em t r ê s a l go r i tmo s imp l em en t ad os n a l i ng uag em c . 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 4 
 
S UM Á RI O 
1 IN T R O DU ÇÃ O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 05 
2 O Q UE É UM A LG O R ÍT MO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 6 
2 A N Á LIS E D E A LG O R ÍT MO S. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 
2 N O TAÇ ÃO ASS IN T Ó T IC A . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 
3 COMPLEXIDADE DE ALGORITMOS............................ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 
4 A LG O R Í T M O DE O R DE N AÇ ÃO QU IC KS ORT. . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 
7 A LG O R IT M O DE O R DE N AÇ ÃO BOLHA.............. . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 
8 C O NC LU S Ã O. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 
9 R EF ERÊ NC IA B IB LIO G R Á F IC A . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 8 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 5 
 
INTRODUÇÃO 
 
U m pr ob l em a p od e se r r es o l v i do d e vá r i as f o rm a s , en t ão v amo s u s a r 
o con ce i to d e an á l i s e d e a l go r i tm os p a r a de t e r min a r a s me lh o re s 
s o l u çõ es , com o o d e s emp enh o d o a lg o r i t mo va r i a conf o rm e a s u a 
en t r ad a e a conf i gu r ação d a m esm a , vamo s u s a r an á l i s e d e 
co mpl ex i d ad e p a r a d e t e r min a r o s eu cus to . 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 6 
 
 
 
 
O QUE É UM ALGORÍTMO? 
 
O algoritmo é um procedimento, passo a passo, para a resolução de um problema em um 
tempo finito, além disso, ele é tratado como a estrutura lógica fundamental na computação e a 
sua construção é composta por uma forma sistemática de organização que proporciona um 
melhor acesso aos seus dados, essa forma é chamada de estruturas de dados. 
 Não existe subjetividade na resolução de um problema por meio algoritmo, ou o 
problema é tratável ou não. Como existem diversas soluções, temos diferentes níveis de 
eficiência que precisam ser adequadas para diversas objeções. Essa adequação é determinada 
segundo alguns critérios, os principais são o tempo e a quantidade de memória usada pelo 
algoritmo no decorrer da solução. 
 O algoritmo pode ser representado de várias formas, a seguir, veremos que formas são 
essas e qual a importâncias delas na análise de algoritmos. 
 
REPRESENTAÇÃO DE ALGORITMOS 
 
Existem algoritmos mais difíceis de ser entendida por isso a necessidade da representação 
deles em outras linguagens com um nível de abstração mais alta.As representações mais 
conhecidas são o fluxograma convencional, descrição narrativa, pseudocódigo e a linguagem 
de programação. 
 
 
 
 
 
 7 
 
DESCRIÇÃO NARRATIVA 
Geralmente usada para descrever passo a passo, seqüência de tarefas com a finalidade de 
se atingir um objetivo, que neste caso é fazer o bolo de milharina. 
 Figura 1 - Bolo de milharina Figura 2 – Receita de Bolo de milharina 
 
 
 
 
 
 
 
FLUXOGRAMA 
É a representação gráfica de um algoritmo através de formas geométricas que são 
interpretadas como ações distintas e facilita o entendimento das idéias contidas no algoritmo, 
aumentando a sua usabilidade. O nível de abstração desta linguagem é maior que as demais 
representações. 
Figura 3 – Formas geométricas e as suas respectivas operações. 
 
 
 8 
 
 Figura 4 - fluxograma de busca Binária Figura 5 - fluxograma de busca seqüencial 
 
 
PSEUDOCÓDIGO 
 
É uma forma genérica de escrever um algoritmo, utilizando uma linguagem simples e de fácil 
entendimento, um exemplo claro de pseudocódigos é o portugol. Nesta linguagem se conta 
com algumas técnicas de organização e identificação do código, como por exemplo, a 
endentação, que serve para identificar estruturas de laço e decisão. 
Outra forma de descrever um algoritmo é através da linguagem de programação que é 
basicamente um conjunto de regras sintáticas e semânticas usadas para definir um programa 
de computador. 
 
 Figura 7 – Exemplo de código escrito em Matlab 
 
 
 
 
 9 
 
 
ANÁLISE DE ALGORÍTMOS 
No mundo real, um problema pode ser solucionado de várias maneiras, isto também reflete de 
alguma forma no mundo digital, a única diferença é que o problema passa a ser solucionado 
através de algoritmos, como há várias alternativas de solução, usa-se a análise de algoritmos 
para determinar o algoritmo mais eficiente. Analisar um algoritmo significa determinar quais 
recursos computacionais serão consumidos por ele, na sua execução. 
Verá mais a frente que esses recursos podem ser medidos e os seus resultados determinaram a 
eficiência do algoritmo. Existem várias técnicas de análise para determinar a eficiência de um 
Algoritmo, mas os principais são por tempo e por quantidade memória. 
A análise que será abordada será por tempo, e o objetivo dessa análise é obter uma expressão 
ou fórmula matemática que represente o tempo de execução de um algoritmo. Os aspectos 
mais importantes da análise de tempo são: 
 A quantidade de elementos que serão processados. 
 A forma como os elementos estão configurados na entrada. 
 
O tempo de execução do algoritmo, na análise é escrito em função do tamanho da entrada e 
escreve-se como f(n), onde n é o tamanho da entrada e f é o numero de operações processados 
pelo algoritmo. A entrada depende do problema que está sendo solucionado pelo algoritmo e 
ela é analisada em três casos, o pior, médio e o melhor. O teste mais eficiente é a análise feita 
utilizando o pior caso, que consiste em encontrar uma entrada com alto nível de complexidade 
e aplicá-la no algoritmo e a partir daí medir a sua eficiência em função do número de passos. 
A seguir compararemos dois algoritmos de ordenação e vamos aplicar a análise utilizando o 
pior caso e definir o mais eficiente. 
 
NOTAÇÃO ASSINTÓTICA 
É uma notação matemática utilizada para analisar o comportamento assintótico de funções, e 
seráutilizada na análise de algoritmo para representar o comportamento das operações do 
algoritmo associado com a entrada, na tentativa de simplificar o comportamento das 
operações do algoritmo relacionado com a sua entrada, a definição da notação O procura uma 
função que seja limitada superiormente pela função f(n), ou seja, g(n) é a derivada de f(x). 
 
 
 10 
Tabela 1- Exemplos de uso da notação assintótica 
notação nome 
O(1) ordem constante 
O(log x) ordem logarítmica 
O([log x]
c
) ordem poli-logarítmica 
O(x) ordem linear 
O(x · log x) ordem linear-logarítmica 
O(x²) ordem quadrática 
O(x³) ordem cúbica 
O(x
c
) ordem polinomial 
O(c
x
) ordem exponencial 
O(x!) ordem fatorial 
O(x
x
) ordem exponencial 
 
 
 
COMPLEXIDADE DE ALGORITMOS 
A notação O descreve o comportamento da entrada n do algoritmo associando-a a uma outra 
função limitada superiormente pela função que descreve o tamanho da entrada de um 
algoritmo.O comportamento dessa função limitada superiormente será analisada em três 
casos, no pior, médio e no melhor caso, utilizando o custo ou complexidade em função do 
tempo ou do espaço usado na memória.Veremos que o algoritmo possui comportamentos 
diferentes nos três casos. 
MÉTODO DE ORDENAÇÃO QUICKSORT 
É um método de ordenação por troca. Entretanto, enquanto o bubblesort (bolha) troca 
pares de elementos consecutivos, o quicksort compara pares de elementos distantes, o que 
acelera o processo de ordenação. É um algoritmo de troca do tipo “dividir para conquistar” 
que resolve um determinado problema, dividindo-o em três subproblemas, tais que: o 
primeiro subproblema é composto dos elementos menores ou iguais ao elemento escolhido 
arbitrariamente, o segundo subproblema é o próprio elemento escolhido e o terceiro 
subproblema são os elementos maiores ou iguais ao elemento escolhido. A seguir, os 
problemas menores são ordenados independentemente e depois os resultados são combinados 
para produzir a solução do problema maior. 
O primeiro passo do algoritmo é crucial, por enquanto não será especificado como 
escolher o elemento, pois o algoritmo funciona independentemente do elemento escolhido 
para ser o pivô. Entretanto, a seleção do pivô afeta diretamente o tempo de processamento do 
algoritmo. 
O método consiste em alocar um determinado elemento em sua posição correta dentro da 
futura lista ordenada, produzindo uma partição da lista em três sub-grupos: 
 11 
 
1. A sub-lista que contém todos os elementos que são menores ou iguais ao elemento 
alocado; 
 
2. A sub-lista formada somente pelo elemento alocado; 
 
 
3. A sub-lista que contém todos os elementos que são maiores ou iguais ao elemento 
alocado. 
 
 
Método de ordenação kicksort com chamada recursiva 
 
 
Vamos analisar a complexidade (custo) do algoritmo acima em relação ao movimento de 
registros. O movimento do registro é sempre superior ao numero de comparações. 
Qualquer que seja a entrada, após a primeira escolha do pivô, será efetuado no máximo n+1 
comparação, pois o elemento é deslocado quando i torna-se maior ou igual a j então temos 
que: 
C(n)<=n+1+C(n1)+C(n2), com n1+n2=n-1. 
Análise utilizando o pior caso: 
 O pior caso ocorre quando os elementos do vetor estão ordenados ou invertidos, pois a cada 
partição resulta uma coleção vazia de elementos. Então após cada varredura resulta n1=0 e 
 12 
n2=0; Daí pode escrever que: 
C(n) n + 1 + C(n – 1) 
C(n – 1) n + C(n – 2) 
C(n – 2) n – 1 + C(n – 3) 
. . . 
C(2) 3 + C(1) 
Como C(1) = 0, por substituições sucessivas obtemos: 
C(n) (n + 1) + n + (n – 1) +... + 3 = 1/2 (n – 1) (n + 4) 
Portanto C(n) ½ (n – 1) (n + 4) = O (n2), logo na complexidade no pior caso é O(n2).já no 
caso médio é O(n*log n) 
 
Caso Médio 
Conforme vimos, qualquer que seja a entrada, temos; 
C(n) (n + 1) + C(n1) + C(n2), com n1 + n2 = n – 1 
Como n1 varia desde 0 até (n-1), existem n entradas distintas e 
C(n) n + 1 + C(0) + C(n – 1) 
C(n) n + 1 + C(1) + C(n – 2) 
. . . 
C(n) n + 1 + C(n - 1) + C(0) 
Expressando C(n) em função de todas as entradas possíveis. 
Somando todas as desigualdades e dividindo por n obtemos: 
n-1 
C(n) n + 1 + 2/m C(i) 
i=0 
Multiplicando a primeira por n, a segunda por (n-1) e subtraindo a primeira da segunda, 
conseguimos expressar C(n) em função de C(n-1): 
nC(n) – (n – 1)C(n-1) n(n + 1) – (n - 1)n + 2C(n-1) 
nC(n) 2n + (n + 1)C(n-1) 
(C(n) / (n + 1) ) (2/ (n + 1)) + (C(n-1) / n) 
Desta última desigualdade podemos escrever a seqüência: 
(C(n) / (n + 1)) (2/ (n + 1)) + (C(n-1) / n) 
(C(n-1) / n) (2/ n ) + (C(n-2) / (n – 1)) 
(C(n-2) / (n - 1)) (2/ (n - 1)) + (C(n-3) / (n – 2)) 
. . . 
C(2) / 3 2/3 + C(1) / 2 
Levando em conta que C(1) = 0, por substituições sucessivas obtemos: 
n+1 n+1 
C(n) / (n + 1) 2 / (n + 1) + 2 / n + . . . + 2/3 = 2 1/i 2 ∫dx / x 
i=3 1 
C(n) / (n+1) 2 ln (n+1), isto é C(n) (n+1) log(n+1) 
Portanto, C(n) =>O(n log n) 
 
 
 
 
 
 
 13 
O quicksort é extremamente eficiente para ordenar arquivos de dados. O método 
Necessita de apenas uma pequena pilha como memória auxiliar, e requer cerca de (n log n) 
Operações em média para ordenar n itens. Como aspectos negativos têm-se: 
 
 A versão recursiva do algoritmo tem um pior caso que é O(n2); 
 A implementação do algoritmo é muito delicada e difícil; 
 O método não é estável. 
Uma vez desenvolvida uma implementação robusta para o quicksort, este deve ser o 
algoritmo preferido para a maioria das aplicações. 
 
 
 
MÉTODO DE ORDENAÇÃO BOLHA 
Este método de ordenação compara os elementos adjacentes e troca se o segundo for menor 
que o primeiro, esta operação se repete até o ultimo par de elementos. É possível melhorar a 
implementação anterior, evitando as passagens desnecessárias, através da identificação da 
entrada para informa se ela já está ordenada. Se em uma passagem não houver nenhuma 
troca, isto quer dizer que a entrada já está ordenada, para isso é necessário controlar o número 
de ocorrências de trocas. 
Como o laço interno executa no máximo N-1 comparações então no pior caso, o número de 
comparações será (n-1)*(n-1), portanto O(n^2), onde n^2 é a função limitada superiormente 
pela função f(n)=(n^2-2n+1). 
Vantagens 
1. Simplicidade. 
 
 
2. Exigência de pouco espaço adicional (um registro extra para armazenar os valores 
temporários da troca e diversos variáveis inteiros simples). 
 
 
3. O fato de ser O(n) no caso em que o arquivo está totalmente classificado 
 
 
 
 
 
 
 
 
 14 
 
Algoritmo de ordenação bolha utilizando vetores de inteiros 
 
Figura 9 – Implementação do BUBLESORT em pascal 
 
 
 
 
 
 15 
 
Figura 8 – Gráfico explorando o comportamento do algoritmo Buble sort em diferentes casos 
 
 
 
As operações descritas no gráfico foram feitas via arquivo binário, o gráfico explora o 
comportamento e o custo (complexidade) em relação ao tempo, do algoritmo bublesort, uma 
coisa curiosa é que o custo do algoritmo aumentou para a entrada com valores ordenados, na 
verdade o que aconteceu foi que mesmo com os valores ordenados, todos eles foram 
comparados novamente devido aos dois laços do algoritmo, enquanto que o procedimento 
troca, ou melhor, o movimento de troca teve um custo baixíssimo. 
 
 
 
 
 
 
 
 
 
 16 
 
CONCLUSÃO 
 
A análise de algoritmo permite determinar a eficiência do algoritmo e também propor as 
devidas correções para que a complexidade da sua entrada assuma comportamentos mais 
suaves, Além disso ela nos permite estudar o quanto de recursos que o algoritmo consome em 
diversos cenários, com isso é possível determinar em quais situações o algoritmo poderá ser 
mais eficiente. 
Vimos alguns exemplos de algoritmos de ordenação cuja complexidade se comportava de 
forma logarítmica e em outros casos se comportava de forma quadrática, um algoritmo de 
complexidade logarítmica, por exemplo, é mais eficiente do que um algoritmo de 
complexidade quadrática,se a unidade custo for a quantidade memória por exemplo, ou até 
mesmo por tempo. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 17 
 
 
 
REFERÊNCIAS BIBLIOGRÁFICAS 
 
UFPE, acessado em: 
http://www.cin.ufpe.br/~joa/menu_options/school/cursos/ppd/aulas/complexidade.pdf 
 
Dielano, USP, acessado em: 
http://www.nakano.pro.br/icc2/pub/aula3assintotico/3-Complexidade/3-handout.pdf 
 
Fábio Henrique, acessado em: 
http://dc.uel.br/~dsbizarro/trab/complex.pdf 
 
Walteno Martins, acessado em: 
http://www.waltenomartins.com.br/aa_aps.pdf 
 
 
Mariano, UTFPR, acessado em: 
http://pessoal.utfpr.edu.br/mariano/arquivos/VAS1997_1.pdf 
 
Paulo Feofilof, USP, acessado em: 
http://www.ime.usp.br/~pf/mac5711-2008/slides/AULAS4up.pdf 
 
Wikpedia, acessado em: 
http://pt.wikipedia.org/wiki/Quicksort 
 
Wikpedia, acessado em: 
http://pt.wikipedia.org/wiki/Merge_sort