Aula T05 – BCC202 Aula T05 – BCC202

Análise de Algoritmos (Parte 3)Análise de Algoritmos (Parte 3)

Túlio ToffoloTúlio Toffolowww.decom.ufop.br/toffolowww.decom.ufop.br/toffolo

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

(Continuação)

Comportamento Assintótico de FunçõesComportamento Assintótico de Funções

• Nas aulas passadas aprendemos:

• Como calcular a função de complexidade f(n).

Melhor caso x Caso médio x Pior caso

Qual a influência desta função em algoritmos aplicados sobre problemas de tamanho pequeno?

E sobre problemas grandes?

Estuda-se o comportamento assintótico das funções de custo. O que isto significa?

Qual a função de complexidade para 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]; } }

2*(n-1)

Exemplo - Maior e Menor Elemento (2)

• MaxMin1 pode ser facilmente melhorado: a comparação A[i] < *pMin só é necessária quando a comparação A[i] > *pMax dá falso.

void MaxMin2(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]; else if (A[i] < *pMin) *pMin = A[i]; } }

Qual a função de complexidade para MaxMin2?

Melhor caso: • quando os elementos estão em ordem crescente;• f(n) = n – 1

Pior caso: • quando o maior elemento é o primeiro no vetor;• f(n) = 2(n – 1)

Caso médio:• No caso médio, A[i] é maior do que Max a metade das vezes.• f(n) = 3n/2 – 3/2

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

Comportamento Assintótico de FunçõesComportamento Assintótico de Funções

• Nas aulas passadas também aprendemos:

• Comportamento assintótico das função de complexidade f(n).

Dominação Assintótica

Notação O.

Notação ΩΩ e Notação ӨӨ..

Dominação AssintóticaDominaçã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)|.

Notação ONotaçã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.

Operações com a Notação OOperações com a Notação O

Qual a complexidade da função 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)

Exercício da Última Semana...

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

2

)1(

2

)11)(1(1...210

1

0

nnnnni

n

i

2

2n

O(n) O(n2)

Notação 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)|.

Notação Notação ӨӨ

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

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

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

Notação Notação ӨӨ

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

Seja g(n) = n2 para n par (n ≥ 0) g(n) = n para n ímpar (n ≥ 1).

Neste caso g(n) poderá ser:Ω(n2), se considerarmos

apenas entradas pares

Ω(n), se considerarmos apenas entradas ímpares

Se considerarmos qualquer entrada possível, então g(n) é Ω(n)

Perguntas....Perguntas....

• n é O(n log n)? Esta afirmação é útil?

• n3 é Ω(n)? Esta afirmação é útil?

• n é O(n)?

• n é Ω(n)?

• n é ӨӨ(n)?(n)?

• n é ӨӨ(n (n loglog n)? n)?

Data da Prova 1

• Quanto mais longe, mais matéria acumula =(

• Tipo Abstrato de Dados• Análise de Algoritmos

• Função de complexidade• Notações O, Ω e ӨӨ• Classes de comportamento assintótico• Limites inferiores

• Alocação Dinâmica• Recursividade

• Valor: 2,0 pontos

Data da Prova 1

• Site: www.decom.ufop.br/toffolo• Listas de exercício estarão disponíveis ainda hoje no site

• Próximas aulas• Classes de comportamento assintótico• Limites inferiores• Alocação Dinâmica (reforço em TAD e ponteiros)• Recursividade• Aula de dúvidas para a prova

• Sugestão de data para a prova: até dia 21/Setembro

Horários de Monitoria

• Kayran (4h/semana)• Terça-feira: 19h – 21h• Quinta-feira: 19h – 21h

• Tiago (8h/semana)• Segunda-feira: 19h – 21h• Terça-feira: 19h – 21h• Quarta-feira: 19h – 21h• Quinta-feira: 19h – 21h

Aula(s) Extra(s)

• Presença não obrigatória• Tema: Reforço sobre algoritmos e programação

• Interessados:• Enviar e-mail para tulio@toffolo.com.br com o assunto

[BCC202 – Aula Extra]

• Provavelmente próxima sexta-feira (manhã ou tarde).• Data/horário a serem decididos por votação no site:

www.decom.ufop.br/toffolo

Quem vê, entende...Mas é quem faz que aprende!

Exercício 1

void ex1(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;

}}

• Obtenha a função de complexidade f(n) dos algoritmos abaixo. Na função de custo, considere apenas as operações envolvendo as variáveis x e y. Responder também, para cada algoritmo:

• Qual o valor da variável x ao final da execução do algoritmo?

• O algoritmo é O(n2)? É ΩΩ(n3)? • O algoritmo é ӨӨ(n(n3)? void ex2(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;}

Exercício 2

• Indique se as afirmativas a seguir são verdadeiras ou falsas e justifique a sua resposta

• É melhor um algoritmo que requer 2n passos do que um que requer 10n10 passos.

• 2n+1 = O(2n).

• f(n) = O(u(n)) e g(n) = O(v(n)) => f(n) + g(n) = O(u(n) + v(n))

• f(n) = O(u(n)) e g(n) = O(v(n))=> f(n) - g(n) = O(u(n) - v(n))