View
218
Download
0
Category
Preview:
Citation preview
Complexidade de Algoritmos
! Uma característica importante de qualquer algoritmo é seu tempo de execução
! é possível determiná-lo através de métodos empíricos, considerando-se entradas diversas.
! executamos um algoritmo e medimos o tempo de execução
! No entanto, esse tempo está de acordo com o sistema computacional em questão
! é também possível obter este tempo a partir de métodos analíticos
! gostaríamos de ter uma idéia do tempo que leva para executar
2
Complexidade de Algoritmos
! Métodos analíticos ! objetivo: determinar uma expressão matemática que traduza
o comportamento de tempo de um algoritmo.
! o tempo de execução independente:
! do método utilizado
! da linguagem e compiladores empregados
! e das condições locais de processamento
3
Complexidade de Algoritmos
! obter uma expressão matemática não é simples, mesmo considerando uma expressão aproximada
! Várias simplificações são introduzidas
! quantidade de dados a serem manipulados pelo algoritmo é suficientemente grande
! quantidade de dados de entrada reduzida não serão considerados
4
Complexidade de Algoritmos
! somente o comportamento assintótico é avaliado
! derivar o número de passos considerando uma entrada muito grande
! não serão consideradas constantes aditivas ou multiplicativas na expressão considerada
! na verdade não afeta tanto o tempo de execução
5
Complexidade de Algoritmos
! Qual a variável em relação à qual a expressão matemática avaliará o tempo de execução?
! Um algoritmo funciona a partir de uma entrada para produzir uma saída dentro de um tempo
! fornecer o tempo de execução em função da entrada
6
Complexidade de Algoritmos
! O processo de execução de um algoritmo pode ser dividido em etapas elementares - passos
! um número fixo de operações básicas cujo tempo de execução é considerado constante
! a operação básica de maior freqüência de execução do algoritmo é denominada operação dominante
7
Complexidade de Algoritmos
! expressão de tempo de execução
! obtida a menos de constantes aditivas e multiplicativas:
! número de passos
! ≅ número de execuções da operação dominante
! A expressão matemática de avaliação do tempo de execução de um algoritmo
! função que fornece o número de passos efetuados no algoritmo a partir de uma certa entrada
8
Complexidade de Algoritmos
Exemplo ! Inversão de uma seqüência
fim = n/2; for (i=0; I < fim; i++) {
temp = S[i]; S[i] = S[n-1-i]; S[n-1-i] = temp; }
9
Complexidade de Algoritmos
! n = 5 ⇒ troca S[i] por S[n-1-i]
! fim = 2
! i = 0 ⇒ troca S[0] por S[5-1-0] (S[4])
! i = 1 ⇒ troca S[1] por S[5-1-1] (S[3])
inicial final
10
M A A R I
0 4 1 2 3
A M I R A
0 4 1 2 3
Complexidade de Algoritmos
! n = 6 ⇒ troca S[i] por S[n-1-i] ! fim = 3 ! i = 0 ⇒ troca S[0] por S[6-1-0] (S[5]) ! i = 1 ⇒ troca S[1] por S[6-1-1] (S[4]) ! i = 2 ⇒ troca S[2] por S[6-1-2] (S[3])
inicial final
11
E D S T A
0 4 1 2 3
O S D A T
0 4 1 2 3
O
5
E
5
Complexidade de Algoritmos
! n = 50 ⇒ troca S[i] por S[n-1-i] ! fim = 25 ! i = 0 ⇒ troca S[0] por S[50-1-0] (S[49]) ! i = 1 ⇒ troca S[1] por S[50-1-1] (S[48]) ! i = 2 ⇒ troca S[2] por S[50-1-2] (S[47]) ......... ! i = 23 ⇒ troca S[23] por S[50-1-23] (S[26]) ! i = 24 ⇒ troca S[24] por S[50-1-24] (S[25])
12
Complexidade de Algoritmos
! o algoritmo executa extamente as mesmas operações para seqüências de tamanho n ! cada passo corresponde à troca de posição entre dois
elementos da seqüência
! a execução das três atribuições
! o número de passos é igual ao número de vezes que executa o bloco for ⇒ n/2, n>1
13
Complexidade de Algoritmos
! Problema: determinar a soma C e o produto D de duas matrizes dadas A e B. ! A = (aij) e B = (bij) ambas n x n ! C e D também serão matrizes n x n ! seus elementos podem ser calculados como: ⇒ cij = aij + bij
⇒ dij = ∑aik * bkj 1≤k ≤ n
14
Complexidade de Algoritmos
! Soma for(i=0; i<n; i++) for(j=0; j<n; j++) cij = aij + bij ;
15
! Produto for(i=0; i<n; i++)
for(j=0; j<n; j++){ dij = 0; for(k=0; k<n; k++) dij = dij + aik* bkj; }
Complexidade de Algoritmos
! Seja A um algoritmo
! {E1, ....Em} o conjunto de todas as entradas possíveis de A
! seja ti o número de passos efetuados por A quando a entrada for Ei
16
Complexidade de Algoritmos
! Complexidade do pior caso:
max Ei ∈ E {ti } ! Complexidade do melhor caso:
min Ei ∈ E {ti }
17
Complexidade de Algoritmos
! Complexidade de tempo do pior caso
! para a entrada mais desfavorável
! é a mais importante das três mencionadas
! fornece um limite superior para o número de passos
! Iremos analisar nossos algoritmos em relação a complexidade de pior caso, como sendo a ordem do número de passos no caso desfavorável
! utilizaremos a notação O()
18
19
Qual melhor algoritmo?
! Sejam A e B dois algoritmos que o resolvem o problema P, cujos tempos de execução são
TA(n) e TB(n)
! comportamento assintótico – tamanho da entrada arbitrariamente grande ! caracterizado pela notação O (big O)
20
A notação Ο
! Sejam f(n) e h(n) funções reais não negativas da variável inteira n ≥ 0
! f(n) = O (h(n)) quando existir uma constante c > 0 e um valor inteiro no tal que
n > no ⇒ f(n) ≤ c.h(n)
21
A notação Ο
f(n) = 8n + 128 ⇒ é O (n2)? f(n) ≤ c.n2 ?
! Seja c =1 8n + 128 ≤ n2, então 0 ≤ n2 – 8n – 128 0 ≤ (n – 16)(n+8) ⇒ n0 = 16 ⇒ c =1, no = 16, f (n) ≤ c.n2 para todo n ≥ n0
22
A notação Ο
f(n) = 8n + 128 ⇒ é O (n2)? f(n) ≤ c.n2 ?
! Então, com c =1 n=8, temos 8n + 128 ≤ n2 ?
23
A notação Ο
f(n) = 8n + 128 ⇒ é O (n2)? f(n) ≤ c.n2 ?
! Então, com c =1 n=8, temos 8n + 128 ≤ n2 ? 8 (8) + 128 ≤ (8)2? 64 + 128 ≤ 128?
24
A notação Ο
f(n) = 8n + 128 ⇒ é O (n2)? f(n) ≤ c.n2 ?
! Então, com c =1 n=8, temos 8n + 128 ≤ n2 ? 8 (8) + 128 ≤ (8)2? 64 + 128 ≤ 128?
25
A notação Ο
f(n) = 8n + 128 ⇒ é O (n2)? f(n) ≤ c.n2 ?
! Então, com c =1 n=20, temos 8n + 128 ≤ n2 ?
26
A notação Ο
f(n) = 8n + 128 ⇒ é O (n2)? f(n) ≤ c.n2 ?
! Então, com c =1 n=20, temos 8n + 128 ≤ n2 ? 8 (20) + 128 ≤ 202 ? 160 + 128 ≤ 400?
27
A notação Ο
f(n) = 8n + 128 ⇒ é O (n2)? f(n) ≤ c.n2 ?
! Então, com c =1 n=20, temos 8n + 128 ≤ n2 ? 8 (20) + 128 ≤ 202 ? 160 + 128 ≤ 400? OK!!!
28
A notação Ο
! Tempo (ou espaço) é contabilizado em número de passos do algoritmo (unidade de armazenamento)
! Análise do algoritmo determina uma função que depende do tamanho da entrada n.
10n3 + 4n -10 ! à medida que n aumenta, o termo cúbico começa
a dominar ! A constante do termo cúbico tem relativamente a
mesma importância que a velocidade da CPU
29
A notação Ο
! Complexidade de pior caso
! desprezar constantes aditivas ou multiplicativas
! número de passos 3n será aproximado para n
! interesse assintótico: termos de menor grau podem ser desprezados:
! n2 + n será aproximado para n2
! 6n3 + 4n - 9 será aproximado para n3
30
A notação Ο
! A função atua como um limite superior assintótico da função f ! f = n2 -1 ⇒ f = Ο(n2)
! f = n2 -1 ⇒ f = Ο(n3)
! f = 403 ⇒ f = Ο(1)
! f = 5+2logn +3log2n ⇒ f = Ο(log2n)
! f = 5+2 log n +3log2n ⇒ f = Ο(n)
! f = 5.2n +5n10 ⇒ f = Ο(2n)
31
A notação Ο
! constantes são ignoradas e somente a função que cresce mais rápido é considerada
função Ο() 3 + 2n Ο( ) 200n3 Ο( ) 0.1 n Ο( ) 101000 Ο( )
2n + 999 Ο( ) 2n + 999n Ο( )
log n + n999 Ο( )
32
A notação Ο
! constantes são ignoradas e somente a função que cresce mais rápido é considerada
função Ο() 3 + 2n Ο(n) 200n3 Ο(n3) 0.1 n Ο(n) 101000 Ο(1)
2n + 999 Ο(n) 2n + 999n Ο(2n)
log n + n999 Ο(n999)
33
A notação Ο! g(n), h(n) - funções reais positivas ! k - constante ! f1(n) = g(n) e f2(n) = h(n)
! O(g+h) = O(g) + O(h)
! O(k*g) = k O(g) = O(g)
! f1(n) + f2(n) = O(max {g(n), h(n)})
! f1(n) * f2(n) = O(g(n) * h(n))
34
A notação Ο! O algoritmo de inversão de uma seqüência:
! o número de passos se mantém o mesmo para o mesmo valor de n
! variável independente é n
! as complexidades de pior, melhor e pior casos são iguais
35
A notação Ο! Para a inversão
! efetua sempre n/2 passos então sua complexidade é Ο(n)
! Para a soma e o produto de matrizes n x n verifica-se complexidades ! Ο(n2) e Ο(n3) respectivamente
36
A notação Ο! por outro lado, um outro exemplo:
! duas matrizes A e B de dimensões n x n
! um parâmetro x, com valores 0 ou 1
! dependendo do valor de x
! calcula a soma: se x =0 " A + B
! ou o produto das matrizes: se x = 1" A * B
37
A notação Ο! entrada: n2+1 informações - tamanho O(n2) ! se x =0 então complexidade: O(n2)
! complexidade do melhor caso ! se x = 1 então complexidade: O(n3)
! complexidade do pior caso
38
Alguns conceitos
T(n) notação
O (1) constante O (log log n) super-rápido
O (log n) logarítmico – muito bom O (n) linear – toda a entrada é visitada
O (n log n) limite de muitos problemas
O (n2) quadrático O (nk) polinomial no tamanho da entrada
O (kn), O (n!), O (nn) exponencial – ruim!
40
Recursividade
! um procedimento recursivo é aquele que contém uma ou mais chamadas a si mesmo
! a todo procedimento recursivo corresponde um não recursivo
! os programas recursivos são mais concisos
! relação direta com a prova por indução matemática
42
Recursividade
Implementação não recursiva
x! = se x <=0 1 senão x * (x-1)!
int fatorial (int N) { int result = 1;
for (i=1; i<=N; i++) result = result * i; return (result);
}
43
Recursividade
Implementação recursiva
x! = se x <=0 1 senão x * (x-1)! int fatorial (int N) {
if (N<= 1) return(1); else return( N * fatorial(N-1));
}
44
Recursividade
! X= fatorial (4)
! return( 4* fatorial(3) )
! return( 3* fatorial(2) )
! return( 2* fatorial(1) )
! return( 1 )
45
Análise da complexidade
# relação de recorrência ● a função é definida em termos dela própria, recursivamente
! substituição repetida int fatorial (int N) { if (N<= 1) return(1); else return( N * fatorial(N-1)); }
46
T(n) ! tempo de processar o algoritmo para entrada n ! número de passos ou operações dominantes
Fatorial T(n) = 1, se n = 0
= T(n-1) + 1, se n > 0
mas quanto é T(n-1) ?
int fatorial (int N) { if (N<= 1) return(1); else
return( N * fatorial(N-1));
}
Análise da complexidade
47
Passos iteração
= (T(n-1)) + 1 - 1ª substituição
= (T(n-2) + 1) + 1
= T(n-2) + 2
Análise da complexidade
48
Passos iteração
= (T(n-1)) + 1 - 1ª substituição
= (T(n-2) + 1) + 1
= T(n-2) + 2 - 2ª substitição
= (T(n-3) + 1) + 2
= T(n-3) + 3
Análise da complexidade
49
Passos iteração
= (T(n-1)) + 1 - 1ª substituição
= (T(n-2) + 1) + 1
= T(n-2) + 2 - 2ª substitição
= (T(n-3) + 1) + 2
= T(n-3) + 3 - 3ª substituição
Análise da complexidade
50
Passos iteração
= (T(n-1)) + 1 - 1ª substituição
= (T(n-2) + 1) + 1
= T(n-2) + 2 - 2ª substitição
= (T(n-3) + 1) + 2
= T(n-3) + 3 - 3ª substituição
..... ....
= T(n-k) + k - k-ésima substituição
Análise da complexidade
51
! Então, T(n) = T(n-k) + k, 1 ≤ k ≤ n ! se a k-ésima interação é a última, então:
! n-k = 0 e T(0) = 1
! Assim, n = k, e T(n) = n + 1
Análise da complexidade
52
Resolva as recorrências
! T(n) = 1, se n = 0 = 2 T(n-1) + 1, se n >0
! T(n) = 1 se n = 1 = T(n/2) + 1 se n>1
! T(n) = 1 se n = 1 = 2T(n/2) - n se n > 1
Recommended