Ciencia_Da_Computacao_Software2

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Análise de algoritmos
Análise de Complexidade de um algoritmo 
A análise de complexidade de um algoritmo tem por objetivo a obtenção de  estimativas de tempos de execução de programas que implementam esse algoritmo (Parreira Jr, 2014).  
A complexidade do algoritmo dá ideia do esforço computacional do programa, que é uma medida do número de operações executadas (instruções) pelo programa. 
São consideradas somente as instruções relevantes, isto é, as operações básicas para a execução do algoritmo. 
O número de vezes que essas operações são executadas é denominado Complexidade do Algoritmo.  
Análise de Complexidade de um algoritmo 
A  complexidade de um algoritmo depende da entrada e esta é caracterizada pelo seu tamanho (quantidade de dados), por seus valores e também pela configuração dos dados.
De  forma  intuitiva,  sabemos  que  a  complexidade  depende  da  quantidade  de  dados  que são processados, isto é, o tamanho da entrada impacta na complexidade. 
Por exemplo: O número de operações executadas para localizar o último registro de uma lista com 1000 registros deve ser maior que o de uma lista com apenas 10 registros.  
Análise de Complexidade de um algoritmo 
Contudo, em algumas situações,  o arranjo (configuração) dos dados na entrada determina o esforço do algoritmo. 
Por exemplo, na execução de uma busca em uma lista linear não ordenada, o número de comparações executadas varia muito conforme o valor procurado ocorrer no primeiro registro, no último ou nos registros intermediários. 
Outro exemplo, nos algoritmos que executam operações sobre listas lineares, a complexidade é expressa em função do tamanho da lista .
Se n indica o número de registros, temos que a complexidade será uma função de n.
Análise de Complexidade de um algoritmo 
Contudo, como a configuração dos dados de entrada são fatores que também interferem no processo, não é possível obter uma única função que descreva todos os casos possíveis. 
Para cada possibilidade de entrada há uma função de complexidade do algoritmo. 
Quando a configuração dos dados de entrada inviabiliza a representação do esforço do algoritmo a partir de uma única função de complexidade, o estudo é reduzido para alguns casos especiais, quais sejam: 
Análise de Complexidade de um algoritmo 
Pior Caso, caracterizado por entradas que resultam em maior crescimento do número de operações, conforme o valor de n aumenta; 
Melhor Caso, caracterizado por entradas que resultam em menor crescimento do número de operações, conforme o valor de n cresce; 
Caso Médio, que reflete o comportamento médio do algoritmo, quando são consideradas todas as entradas possíveis e as respectivas probabilidades de ocorrência. 
Concluindo, Somente o estudo da complexidade de algoritmos permite a comparação de dois algoritmos equivalentes, isto é, desenvolvidos para resolver o mesmo problema.  
Notação big O
A notação O (leia-se  big o) é utilizada para expressar comparativamente o crescimento assintótico. 
Representa a velocidade com que uma função tende ao infinito. 
No estudo de complexidade de algoritmos é mais interessante saber como se comporta essa função à medida que a entrada n aumenta "exageradamente", do que conhecer valores da função correspondentes a valores particulares de n. 
É mais importante, por exemplo, saber que o número de operações executadas num algoritmo dobra se  o valor de n é duplicado, do que saber que para n igual a 100 são executadas 300 operações.
Notação big O
Quando se afirma que uma função de complexidade f(n) é da ordem de n2, o entendimento é que as duas funções, f(n) e n2 tendem ao infinito com a mesma velocidade, ou que têm o mesmo comportamento assintótico. 
Matematicamente, f(n) = O(n2) se, e somente se, 
Se, outro algoritmo para o mesmo problema tem função de complexidade f1(n) = O(n), pode-se comparar f(n) e f1(n) e, consequentemente, comparar a eficiência dos algoritmos. 
Em um deles, o tempo de execução é linear e no outro, o tempo é quadrático. 
Notação big O: Exemplos de complexidades
O(n) (linear): é aquele cujo crescimento no número de operações é diretamente proporcional ao crescimento dos dados de entrada n. 
Exemplo: Algoritmos de busca em num array (vetor) não ordenado.
 
O(log n) (logaritmo): Nesta complexidade o crescimento do número de operações é menor do que a quantidades de dados de entrada n, isto é:
Exemplo: algoritmos de busca em árvores binárias ordenadas
 
O(1) (constante): Em algoritmos com complexidade constante não há crescimento do número de operações, pois o total de operações independe do volume de dados de entrada (n). Exemplos: Acesso direto a um elemento de uma matriz ou de inserção ou remoção de um elemento em uma pilha ou em uma fila.
	n	logn
	1	0
	10	1
	100	2
	1000	3
Notação big O: Exemplos de complexidades
O(n2) (quadrático): Complexidade aceitável, mas o algoritmo tende a ser lento quando a quantidade de dados é suficientemente grande. 
Exemplo: Algoritmos que têm dois laços de repetição encadeados empregados no processamento de itens em uma matriz bidimensional. 
O(n log n) (sub-quadrático ou super-linear): É uma complexidade melhor do que a quadrática, sendo geralmente até onde se consegue otimizar algoritmos de comlexidae quadrática. 
O algoritmo de ordenação QuickSort, por exemplo (que tem essa complexidade no caso médio, mas que ainda assim é quadrático no pior caso). 
	n	n2
	1	0
	10	100
	100	10000
	1000	1000000
Avaliação da complexidade de algoritmos com a notação O 
Para ilustrar o emprego da notação O na avaliação da complexidade de algoritmos, considere os dois algoritmos a seguir que fazem respectivamente soma e multiplicação de matrizes quadradas.
Uma proposta simples de adição entre duas matrizes quadradas m1 e m2 é somar os elementos de m1 com os correspondentes elementos de m2 e colocar o resultado da soma numa terceira matriz m3.
Avaliação da complexidade de algoritmos com a notação O 
Análise: 
O “enquanto” externo (linha 2) é dependente do tamanho da matriz. 
Para cada execução dessa estrutura de repetição, deve-se executar o “enquanto” mais interno (linha 4) que também depende do tamanho da matriz. 
m3 = m1 + m2
Na linha 2, a estrutura de repetição enquanto percorre a matriz de 1 até N
Para cada incremento da linha 2, a linha 4 percorre a matriz de 1 a N (portanto N execuções), onde N é o tamanho da matriz, 
Logo N x N = N2. 
O que caracteriza uma situação clássica da repetição quadrática, ou seja, a eficiência do algoritmo (complexidade) é O(n2). 
Avaliação da complexidade de algoritmos com a notação O 
m3 = m1 * m2
Uma proposta simples de algoritmo de multiplicação  de matrizes quadradas (m1 e m2) é construir a matriz m3 a partir do produto interno, nesta ordem, entre todas as colunas de m1 com cada linha de m2.
Avaliação da complexidade de algoritmos com a notação O 
Executando a linha 8 para duas matrizes quadradas de ordem 2 (n = 2), tem-se: 
m3 [1,1] = m1[1,1]*m2[1,1] + m1[1,2]*m2[2,1]
m3 [1,2] = m1[1,1]*m2[1,2] + m1[1,2]*m2[2,2]
m3 [2,1] = m1[2,1]*m2[1,1] + m1[2,2]*m2[2,1]
m3 [2,2] = m1[2,1]*m2[1,2] + m1[2,2]*m2[2,2]
Total de multiplicações: 8 = 23 
Total de adições: 4 =  22(2-1) = 4
Executando a linha 8 para duas matrizes quadrada de ordem 3 (n = 3), tem-se:
Total de multiplicações: 27 = 33 
Total de adições: 18 = 32(3-1)
Avaliação da complexidade de algoritmos com a notação O 
Executando a linha 8 para duas matrizes quadradas de ordem n, tem-se: 
Total de multiplicações:   n3 
Total de adições: n2(n-1) 
Complexidade do produto matricial: n3 + n2(n-1), ou seja, O(n3)
Avaliação da complexidade de algoritmos com a notação O 
Outro exemplo para ilustrar os passos a serem executados, para isto, calcular a notação O da seguinte função: f(n) = 4n2 + 2n + 3 
Primeiramente assumir que os coeficientes são iguais a 1, logo f(n) = n2 + n +1; 
em seguida são removidos os fatores de menor importância: f(n) = n2
finalmente, a notação será: O(f(n)) = O(n2) 
Avaliação da complexidade de algoritmos com a notação O 
Análise
de complexidade da Busca Linear 
O algoritmo a ser analisado é o algoritmo de busca da primeira ocorrência de um valor x na lista A. 
Admitindo que A tenha n registros, tem-se o seguinte algoritmo (“BuscaPrimeiraOcorrencia”):
Análise de complexidade da Busca Linear 
A função de complexidade deve indicar, portanto, o número de vezes que é testada a condição (A[j] ≠ x). 
Pior Caso 
A condição A[j] ≠ x ocorre como condição de controle do loop e, mais uma vez após o loop, na instrução de seleção.
( j