Análise de Algoritmos Parte 2 Prof. Túlio Toffolo http://www.toffolo.com.br

BCC202 – Aula 05

Algoritmos e Estruturas de Dados I

Como escolher o algoritmo mais adequado para uma situação?

(continuação)

2

void exercicio1 (int n){ int i, a; a = 0; i = 0; while (i < n) { i += 2; a += i; }}

void exercicio2 (int n){ int i, j, a; a = 0; for (i = 0; i < n; i++) for (j = 0; j < i; j++) a += i + j;}

Exercício da última aula

3

n2!

""#

$$i

i=0

n−1

∑ = 0+1+...+ n−1= n(n−1)2

Perguntas?

Comportamento Assintótico de Funções

•  Na aula passada aprendemos como calcular a função de complexidade f(n).

•  Algumas observações:

Ø  Para valores pequenos de n, praticamente qualquer algoritmo custa pouco para ser executado.

Ø  Logo: a escolha do algoritmo tem pouquíssima influência em problemas de tamanho pequeno.

5

Comportamento Assintótico de Funções

•  A análise de algoritmos deve ser realizada para valores grandes de n.

•  Para isso, estuda-se o comportamento assintótico das funções de custo.

Ø  Comportamento de suas funções para valores grandes de n

•  O comportamento assintótico de f(n) representa o limite do comportamento do custo quando n cresce.

6

Comportamento Assintótico de Funções

•  A análise de um algoritmo geralmente conta com apenas algumas operações elementares.

•  A medida de custo ou medida de complexidade relata o crescimento assintótico da operação considerada.

•  Definição: Uma função f(n) domina assintoticamente outra função g(n) se:

Ø  Existem duas constantes positivas c e m tais que, para n ≥ m, temos |g(n)| ≤ c|f(n)|.

7

Dominação Assintótica

•  f(n) domina assintoticamente g(n) se:

Ø  Existem duas constantes positivas c e m tais que, para n ≥ m, temos |g(n)| ≤ c|f(n)|.

8

Exemplo: n  Sejam g(n) = (n + 1)² e f(n) = n². Exemplo: n  As funções g(n) e f(n) dominam assintoticamente uma

n  Sejam g(n) = (n + 1)² e f(n) = n².

n  As funções g(n) e f(n) dominam assintoticamente uma

a outra, desde que

|g(n)| ≤ c |f(n)|

|g(n)| ≤ c |f(n)| para n ≥ m; c = 1 e m =0 para n ≥ m; c = 1 e m =0

Dominação assintótica

9

Notação O

•  Exemplo: Ø  Quando dizemos que o tempo de execução T(n) de

um programa é O(n²), significa que existem •  Exemplo:

constantes c e m tais que, para valores de n ≥ m,

T(n) ≤ cn². um programa é O(n²), significa que existem constantes c e m tais que, para valores de n ≥ m, T(n) ≤ cn².

10

Notação O

•  Exemplo gráfico de dominação assintótica que ilustra a notação O.

Ø  Abaixo, a função f(n) domina assintoticamente a função g(n).

11

Notação O

•  O valor da constante m mostrado é o menor valor possível, mas qualquer valor maior também é válido.

•  Definição: uma função g(n) é O(f(n)) se existem duas constantes positivas c e m tais que g(n) ≤ c f(n), para todo n ≥ m.

12

Operações com a Notação O

13

Exemplo de Notação O

Exemplo: g(n) = (n+1)2.

•  Logo g(n) é O(n2), quando m = 1 e c = 4.

•  Isto porque (n+1)2 ≤ 4n2 para n ≥ 1.

existe c tal que g(n) ≤ c f(n) para n ≥m

14

Exemplo de Notação O

Exemplo: g(n) = n e f(n) = n2.

•  Sabemos que g(n) é O(n2), pois para n ≥ 1, n ≤ n2.

•  Entretanto f(n) não é O(n).

•  Suponha que existam constantes c e m tais que para todo n ≥ m, n2 ≤ cn.

•  Se c ≥ n para qualquer n ≥ m, então deveria existir um valor para c que possa ser maior ou igual a n para todo n.

não existe c tal que g(n) ≤ c f(n) para n ≥m

15

Exemplo de Notação O

Exemplo: g(n) = 3n3 + 2n2 + n é O(n3).

•  Basta mostrar que 3n3 + 2n2 + n ≤ 6n3, para n ≥ 0

•  A função g(n) = 3n3 + 2n2 + n é também O(n4)entretanto esta afirmação é mais fraca do que dizer que g(n) é O(n3).

•  Pergunta: g(n) é O(n40)?

existe c tal que g(n) ≤ c f(n) para n ≥m

16

Exemplo de Notação O

Exemplo: g(n) = log5n é O(log n).

•  O logbn difere do logcn por uma constante que no caso é logbc.

•  Como n = clogc n, tomando o logaritmo base b em ambos os lados da igualdade, temos que

logbn = logb clogc n logbclogc n= logcn x logbc.

existe c tal que g(n) ≤ c f(n) para n ≥m

17

Qual a complexidade assintótica de MaxMin1

•  Seja f(n) o número de comparações entre os elementos de A, se A contiver n elementos.

•  Logo f(n) = 2(n-1) para n > 0, para o melhor caso, pior caso e caso médio.

void MaxMin1(int* A, int n, int* pMax, int* pMin){ int i; *pMax = A[0]; *pMin = A[0]; for (i = 1; i < n; i++) { if (A[i] > *pMax) *pMax = A[i]; if (A[i] < *pMin) *pMin = A[i]; } }

O(n)

18

void exercicio1 (int n){ int i, a; a = 0; i = 0; while (i < n) { a += i; i += 2; }}

void exercicio2 (int n){ int i, j, a; a = 0; for (i = 0; i < n; i++) for (j = 0; j < i; j++) a += i + j;}

Exercício da última aula

19

⎥⎥

⎤⎢⎢

⎡2

2 n

O(n2) O(n)

ii=0

n−1

∑ = 0+1+...+ n−1= n(n−1)2

Operações com a notação O

•  Exemplo: regra da soma O(f(n)) + O(g(n)).

•  Suponha três trechos cujos tempos de execução são O(n), O(n2) e O(n log n).

•  O tempo de execução dos dois primeiros trechos é O(max(n, n2)), que é O(n2).

•  O tempo de execução de todos os três trechos é então O(max(n2, n log n)), que é O(n2).

20

Notação Ω

•  Especifica um limite inferior para g(n).

•  Definição: Uma função g(n) é Ω(f(n)) se:

Ø  Existem duas constantes positivas c e m tais que, para n ≥ m, temos |g(n)| ≥ c|f(n)|.

•  Exemplo:

Ø  Quando dizemos que o tempo de execução T(n) de um programa é Ω(n²), significa que existem constantes c e m tais que, para valores de n ≥ m, T(n) ≥ cn².

21

Notação Ω

•  Exemplo gráfico de dominação assintótica que ilustra a notação Ω.

Ø  Abaixo, a função f(n) é dominada assintoticamente pela função g(n).

22

Notação Ω

•  Exemplos:

Ø  Para mostrar que g(n) = 3n3 + 2n2 é Ω(n3) basta fazer c = 1, e então 3n3 + 2n2 ≥ n3 para n ≥ 0.

Ø  Seja g(n) = n para n ímpar (n ≥ 1) e g(n) = n2 para n par (n ≥ 0). Neste caso g(n) é Ω(n2), bastando considerar c = 1 e n = 0, 2, 4, 6, …

23

Notação Ө

•  Especifica um limite assintótico firme para g(n).

•  Definição: Uma função g(n) é Ө(f(n)) se:

Ø  Existem três constantes positivas c1, c2 e m tais que, para n ≥ m, temos: 0 ≤ c1f(n) ≤ g(n) ≤ c2f(n).

•  Isto é, para todo n ≥ m, a função g(n) é igual a f(n) a menos de uma constante.

24

Notação Ө

•  Exemplo gráfico de dominação assintótica que ilustra a notação Ө.

Ø  Dizemos que g(n) = Ө(f(n)) se existirem constantes c1, c2 e m tais que, para todo n ≥ m, o valor de g(n) está sobre ou acima de c1f(n) e sobre ou abaixo de c2f(n).

25

Notação Ө

•  Para ser Ө(f(n)), uma função deve ser ao mesmo tempo O(f(n)) e Ω(f(n)).

•  Exemplos:

Ø  Para mostrar que g(n) = 3n3 + 2n2 é Ω(n3) basta fazer: c = 1, e então 3n3 + 2n2 ≥ n3 para n ≥ 0.

Ø  Seja g(n) = n para n ímpar (n ≥ 1) e g(n) = n2 para n par (n ≥ 0). Neste caso g(n) é Ω(n2), bastando considerar c = 1 e n = 0, 2, 4, 6, …

26

Exemplo: Algoritmos MinMax

•  Todos os algoritmos tem a mesma complexidade assintótica, ou seja:

•  Todos são O(n), Ω(n) e, portanto, Ө(n)

27

Perguntas?

Exercício

•  Obtenha a função de complexidade f(n) dos algoritmos abaixo. Considere apenas as operações envolvendo as variáveis x e y. Para cada algoritmo, responda:

•  O algoritmo é O(n2)? É Ω(n3)?

•  O algoritmo é Ө(n3)?

void exercicio1(int n) { int i, j, x, y; x = y = 0; for (i = 1; i <= n; i++) { for (j = i; j <= n; j++) x = x + 1; for (j = 1; j < i; j++) y = y + 1; }}

void exercicio2(int n) { int i, j, k, x; x = 0; for (i = 1; i <= n; i++) for (j = 1; j <= n; j++) for (k = 1; k <= j; k++) x = x + j + k; x = i;}