ESTRUTURA DE DADOSboeres/slides_ed/ed2.pdf · ESTRUTURA DE DADOS Algoritmos – alguns conceitos Cristina Boeres . Complexidade de Algoritmos ! Uma característica importante de qualquer

ESTRUTURA DE DADOS

Algoritmos – alguns conceitos

Cristina Boeres

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


!  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


!  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


!  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


!  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


!  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


!  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


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


!  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


!  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


!  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


!  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


!  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


!  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; }


!  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 do pior caso:

max Ei ∈ E {ti } !  Complexidade do melhor caso:

min Ei ∈ E {ti }

17


!  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 Ο

!  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

23

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

24

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)

25

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 Ο( )

26

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))

27

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

28

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

29

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

30

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

31

Alguns conceitos

!  T (n) = O (1) : constante !  T (n) = O (log log n) : super-rápido !  T (n) = O (log n) : logarítmico – muito bom !  T (n) = O (n) : linear – toda a entrada é visitada !  T (n) = O (n log n) : limite de muitos problemas !  T (n) = O (n2) : quadrático !  T (n) = O (nk) : polinomial no tamanho da entrada !  T (n) = O (kn), O (n!), O (nn) : exponencial – ruim!

Documents

ESTRUTURA DE DADOSboeres/slides_ed/ed2.pdf · ESTRUTURA DE DADOS Algoritmos – alguns conceitos Cristina Boeres . Complexidade de Algoritmos ! Uma característica importante de qualquer