Análise de Algoritmos

Esta é a versão em html do arquivo http://rico_linden.tripod.com/GA/Notacao-O.ppt.
G o o g l e cria automaticamente versões em texto de documentos à medida que vasculha a web.

 
 

Análise de Algoritmos 

Estruturas de Dados e Algoritmos II 

Prof. Ricardo Linden

 

Análise de Algoritmos  

2  

Notação para análise de complexidade 

• Quando estamos analisando a complexidade de um algoritmo, estamos interessados mais no comportamento geral do que nos pequenos detalhes (que variam de máquina para máquina)

 

• Nós gostaríamos de saber quão rápido a complexidade de um algoritmo cresce conforme aumentamos um parâmetro do problema (n - normalmente o tamanho da entrada).

 

• O que realmente nos interessa é a eficiência assintótica dos algoritmos em máquinas que operam no modelo de acesso aleatório

 

Análise de Algoritmos  

3  

Tempo de Execução 

• O tempo de execução de um algoritmo varia (e normalmente cresce) com o tamanho da entrada.

 

• O caso médio é difícil de determinar.

 

• Nós vamos nos concentrar nos tempos máximos, pelos seguintes motivos:

• Mais fácil de analisar.
• É crucial para determinar a qualidade das aplicações.

 

Análise de Algoritmos  

4  

Estudos Experimentais 

• Escreva um programa que implementa o algoritmo.

 

• Execute o programa com entradas de vários tamanhos e tipos diferentes.

 

• Use um método da linguagem de programação para determinar o tempo real de execução.

 

• Desenhe o gráfico dos resultados obtidos.

 

Análise de Algoritmos  

5  

Análise Teórica 

• Leva em consideração todos os tipos de entrada possíveis.

 

• Permite que avaliemos a velocidade do algoritmo de forma independente do ambiente de hardware e software

 

Análise de Algoritmos  

6  

Operações Primitivas 

• Computações básicas realizadas por um algoritmo.

 

• Definição exata não é importante

 

• Contadas como executando em tempo unitário, apesar de obviamente serem diferentes.

 

• Exemplos:

• Avaliando uma expressão.
• Atribuindo um  valor para ma vaiável.
• Chamando uma função
• Escrevendo na tela
• Etc.

 

Análise de Algoritmos  

7  

Contando Operações Primitivas 

• Inspecionando o código, nós podemos determinar o número máximo de operações executados por um algoritmo, como função do tamanho da entrada.

 

int arrayMax(int A[],int n)

{

                                       # operations

    currentMax = A[0];          1

    for(i=1; i<n;i++) {  1+ (repete n-1 vezes)  [ teste(1) e incremento (1)

       if (A[i]  currentMax)      1

       currentMax  A[i];      1

      }      ]

    return currentMax           1

}       Total  (n-1)*4 + 3 = 4n - 1

 

Análise de Algoritmos  

8  

Estimando o tempo de execução 

• O algoritmo arrayMax executa 4n  1 operações primitivas no pior caso

 

• Definimos:

• a    Tempo levado pela operação primitiva mais rápida
• b   Tempo levado pela operação primitiva mais lenta

 

• Seja T(n) o verdadeiro tempo de execução de pior caso da função arrayMax calculado anteriormente. Nós temos: 
  

                a (4n  1)  T(n)  b(4n  1) 

• Logo, o tempo de execução T(n) é limitado por duas funções lineares

 

Análise de Algoritmos  

9  

Taxa de crescimento do tempo de execução 

• Mudando o ambiente de hardware/ software

• Afeta T(n) por um fator constante
• Não altera a taxa de crescimento de T(n)

 

• A taxa de crescimento linear de T(n) é uma propriedade intrínseca do algoritmo arrayMax

 
 
 

Todo algoritmo tem uma taxa de crescimento que lhe é intrínseca - o que varia de ambiente para ambiente é o apenas o tempo absoluto de cada execução, que é absolutamente dependente de fatores como poder de processamento

 

Análise de Algoritmos  

10  

Taxas de crescimento 

• Taxas de crescimento de funções:

• Linear  n
• Quadrática  n²
• Cúbica  n³

 

• No gráfico log-log ao lado, a inclinação da linha corresponde à taxa de crescimento da função.

 

Análise de Algoritmos  

11  

Fatores Constantes 

• A taxa de crescimento não é afetada por:

• fatores constantes
• fatores de mais baixa ordem.

Exemplos

• 10²n + 10⁵ é uma função linear
• 10⁵n² + 10⁸n é uma função quadrática.

 

Análise de Algoritmos  

12  

Notação Big-Oh 

• Dadas as funções f(n) e g(n), nós dizemos que f(n) é O(g(n)) se existem duas constantes não-negativas c e n₀ tais que

 

          f(n)  cg(n)   n  n₀ 

• Exemplo: 2n + 10 é O(n)

2n + 10  cn

(c  2) n  10

n  10/(c  2)

Escolha c = 3 e n₀ = 10 
 

Basta existir um!

 

Análise de Algoritmos  

13  

Notação Big-Oh 

Isto é, uma função f(n) é O(g(n))

se após um determinado ponto n₀

f(n) não é maior que cg(n)

 

Análise de Algoritmos  

14  

Notação Big-Oh 

• Exemplo: a função n² não é O(n)

n²  cn

n  c

     A inequalidade acima não pode ser satisfeita em nenhum caso, dado que c é uma constante.  

Qualquer c que escolhermos

será suplantado por n quando

este tiver valor igual a c+1

 

Análise de Algoritmos  

15  

Outros Exemplos 

f(n) = 12n + 1500  é  O(n²)? 

- 

2.000 

4.000 

6.000 

8.000 

10.000 

12.000 

14.000 

16.000 

18.000 

20.000 

1  

4  

7  

10  

13  

16  

19  

22  

25  

28  

31  

34  

n 

f(n) = 12 n + 1500 

2 n^2 

15 n^2 

2 n 

2 

15 n 

2 

f(n) 

Sim!

 

Análise de Algoritmos  

16  

f(n) = 144 n² – 12 n +50 é O(n²)? 

Outros Exemplos 

Sim!

 

Análise de Algoritmos  

17  

f(n) = n³/100 + 3 n² é O(n²)? 

Sim! 

Têm Certeza???? 

Outros Exemplos

 

Análise de Algoritmos  

18  

Outros Exemplos 

Não!!! 

f(n) = n³/100 + 3 n² é O(n²)?

 

Análise de Algoritmos  

19  

Mais exemplos 

• 6n⁴ + 12 n³ + 12

 

• 3n² + 12 n log n

 

• 5n² + n (log n)² + 12

 

• log n + 4   

 
 

O(n⁴) 

O(n⁵) 

O(n³) 

O(n²) 

O(n⁵) 

O(n) 

O(n²) 

O(n⁵) 

O(log n) 

O(n)

 

Análise de Algoritmos  

20  

Big-Oh e taxa de crescimento 

• A notação big-Oh fornece um limite superior para a taxa de crescimento da função
• A afirmação “f(n) é O(g(n))” significa que a taxa de crescimento de f(n) não é maior que a taxa de crescimento de g(n)
• Nós usamos a notação big-Oh para ordenar as funções de acordo com sua taxa de crescimento

 

Sim 

Sim 

Mesma taxa 

Sim 

Não 

f(n) cresce mais 

Não 

Sim 

g(n) cresce mais 

g(n) é O(f(n)) ? 

f(n) é O(g(n)) ?

 

Análise de Algoritmos  

21  

{n³} 

{n²} 

Classes de Funções 

• Seja {g(n)} o conjunto de funções que são O(g(n))
• Nós temos então o seguinte:

  {n}  {n²}  {n³}  {n⁴}  {n⁵}  …  
(note que cada um dos conjuntos está estritamente contido no seguinte da hierarquia) 

{n}

 

Análise de Algoritmos  

22  

Classes de Funções 

• Isto quer dizer que toda função O(n) também é O(n²), toda função O(n²) também é O(n³), e assim por diante.

 

• Isto é uma decorrência óbvia do fato de n ser sempre não negativo e na verdade nós estarmos procurando valores grandes de n (n)

 

Análise de Algoritmos  

23  

Muita atenção 

• O sinal de igualdade aqui não tem o significado habitual!!!

 

10 n² + 10 log n = O(n²) 

2 n² – 3 = O(n²) 

10 n² + 10 log n = 2 n² – 3

 

Análise de Algoritmos  

24  

Regras do cálculo Big-Oh 

• Se f(n) é uma função polinomial de grau d, então f(n) é O(n^d), isto é:

• Descarte termos de menor ordem
• Descarte termos constantes.

 

• Use o menor conjunto possível.

• Diga “2n é O(n)” em vez de  “2n é O(n²)”

 

• Use a expressão mais simples da classe

• Diga “3n + 5 é O(n)” em vez de “3n + 5 é O(3n)”

 

Algorithm Analysis  

25  

Análise  

• operações consecutivas - some seus tempos:

          for ( int x = 1; x < N; x++ )

                      <operação qualquer>;

    for ( int x = 1; x < N; x++ )

                      for ( int y = 1; y < N; y++ )

                                        <operação qualquer>; 

• tempo total : N + N²  O(N²)

 
 

O(N) 

O(N²)

 

Análise de Algoritmos  

26  

Análise 

• condicional - Nunca maior que o tempo do teste somando ao maior dos tempos dos blocos de operações do condicional

if ( x == y )

    doSomething();

else

    doSomethingElse();

   Big-Oh de doSomething() ou de doSomethingElse() (a maior) 

• Chamadas de função : conte o tempo de execução da função (e não 1, que é o tempo da chamada)

 

Análise de Algoritmos  

27  

Big-Oh 

0 

1 

1 

2 

2 

3 

3 

4 

4 

5 

0 

1 

5 

10 

15 

20 

25 

30 

35 

40 

45 

50 

55 

60 

65 

70 

75 

80 

85 

90 

95 

100 

Entrada - N 

Run Time 

Constant - c 

Logarithmic - log N 

Log-squared - log2 N 

log² N 

log N 

C

 

Análise de Algoritmos  

28  

Big-Oh 

0 

10 

20 

30 

40 

50 

60 

70 

80 

90 

0 

1 

5 

10 

15 

20 

25 

30 

35 

40 

45 

50 

Entrada - N 

Run Time 

Constant - c 

Logarithmic - log N 

Log-squared - log2 N 

Linear - N 

N log N 

Constant 

log N 

N 

N log N 

log² N

 

Análise de Algoritmos  

29  

Big-Oh 

0 

5000 

10000 

15000 

20000 

25000 

30000 

35000 

0 

1 

5 

10 

15 

Entrada - N 

Run Time 

Quadrática - N² 

Cúbica - N³ 

Exponencial - 2^N 

Exponencial - 2^N 

Cúbica - N³ 

Quadrática - N²

 

Análise de Algoritmos  

30  

Big-Oh 

Baseados nos gráficos, vemos que podemos classificar as funções em ordem crescente de tempo de execução

• Esta ordem pode ser dada por:

• Constante  O(c)
• Logarítmica  log N
• Log-quadrada  log²N
• Linear   N
• N log N   N log N
• Quadrática  N²
• Cúbica   N³
• Exponencial  2^N

 

Análise de Algoritmos  

31  

Análise Assintótica de Algoritmos  

• A análise assintótica de algoritmos descreve o tempo de execução em notação big-Oh
• Para realizar a análise assintótica:

• Calculamos o número de operações primitivas executadas como função do tamanho da entrada.
• Expressamos esta função na notação big-Oh

Exemplo:

• Determinamos que o algoritmo arrayMax executa no máximo 4n  1 operações primitivas
• Logo, dizemos que o algoritmo arrayMax “executa em tempo O(n)”

 

Análise de Algoritmos  

32  

Análise Assintótica de Algoritmos 

• Com a notação Big-Oh nós só estamos preocupados com o termo dominante. Por exemplo:

• Quadrática -  provavelmente é C₁N² + C₂N + C₃
• Cúbica - provavelmente é C₁N³ + C₂N² + C₃N + C₄

 

• Novamente, nossa preocupação com os tempos só passa a ser relevante quando o n cresce muito e:

 

                lim _n  (n/n²) = 0 (por L’Hôpital) 

 

Análise de Algoritmos  

33  

• É da aplicação de limites que tiramos os fundamentos teóricos para determinação de f(n) ser ou não g(n).

 

• Basicamente, podemos determinar que f(n) é O(g(n)) se e somente se:

                    lim _n  (f(n)/g(n)) = c 
 

Análise Assintótica de Algoritmos 

Note que alguns livros usam 0 ao invés de c mas isto faria com que f(n) não fosse da ordem de f(n), o que é um erro.

 

Análise de Algoritmos  

34  

Limites inferiores 

• A notação O fornece limites superiores para o crescimento de nossas funções, mas existem outras notações que podem fornecer mais informações interessantes sobre o crescimento do tempo de execução de nossos algoritmos.

 

• Seja (g(n)) o conjunto de funções f(n) para as quais existem constantes não negativas c e n₀ tais que:

          f(n)  cg(n)   n  n₀ 

g(n) fornece um limite inferior para o crescimento de f(n)

 

Análise de Algoritmos  

35  

Exemplos 

• f(n) = 12 n² – 10  (1)

 

• f(n) = 12 n² – 10  (n)

 

• f(n) = 12 n² – 10  (n²)

 

• Entretanto f(n) = 12 n² – 10  (n³)

 

Análise de Algoritmos  

36  

Na prática … 

• Para g(n) nós usamos a maior função que seja adequada

 
 
 
 

Dizer que f(n) = 3n² + 10 =  (1) é correto,, mas não nos fornece muita informação sobre f(n)! 

• Para g(n) nós usamos o termo de crescimento mais rápido em f(n)
• Nós escrevemos f(n) = (g(n)) ao invés do mais correto f(n)  (g(n))

 

Análise de Algoritmos  

37  

Quando os limites inferiores e superiores coincidem... 

• Quando uma função pertence simultaneamente a O(g(n)) e a (g(n)) dizemos que f(n)  (g(n))

 

Mais precisamente, o conjunto (g(n)) é o conjunto de todas as funções para as quais existem constantes não negativas c₁, c₂, n₀ tais que:

c₁g(n)  f(n)   c₂g(n)    n  n₀ 

f(n) = (g(n))

spanspan Posted via web from jamil's posterous