Tutoria AEDSIPablo Silva

Recordar é viver

• Definição de algoritmo• Definição de tipo de dado• Definição de TAD• Análise de algoritmos

Hoje

• Análise da complexidade de algoritmos

• Resolver exercícios

Mas antes...Uma definição mais simples do que é tipo de dado (pra responder na prova se cair!!!):

• Em linguagens de programação o tipo de dado de uma variável, constante ou função define o conjunto de valores que a variável, constante ou função pode assumir.• Ex.: variável boolean pode assumir valores true ou false.

Portanto true e false é o conjunto de valores de uma variável booleana.

Por que analisar um algoritmo?

Depois que decidimos qual o problema que queremos resolver (Ex. encontrar um elemento num conjunto de valores), precisamos ter certeza que o algoritmo escolhido para o nosso problema, irá resolvê-lo em um espaço de tempo e consumir memória, num intervalo de tempo e quantidade de memória gastas aceitáveis para nosso cliente.

Por que analisar um algoritmo?

Nenhum cliente vai querer um programa que demora 10 minutos para encontrar um elemento dentro de um conjunto de valores!

Isso é perda de dinheiro e tempo, uma vez que deve existir um algoritmo que faça isso em poucos milissegundos!

Por que analisar um algoritmo?

No final, o que vai importar na análise é qual o caso médio que tal algoritmo demora para nos dar a saída do problema!

Passos para analisar um algoritmo e decidir os três casos

1. Entenda o problema: sem entender o problema é praticamente impossível determinar os três casos corretamente.

Entendendo o problemaSe temos o problema de encontrar um elemento num conjunto de valores, entender o problema significa:

Talvez o elemento procurado esteja na primeira posição buscada, ou talvez esteja na última. Mas ele pode também estar no meio ou próximo de lá.

Dessa maneira já sabemos qual os nossos melhor caso, pior caso e caso médio respectivamente. Agora só precisamos encontrar uma maneira de representa-los matematicamente.

Passos para analisar um algoritmo e decidir os três casos

2. Encontre no algoritmo loops e estruturas condicionais. ESQUEÇA O RESTO!

Encontre loops e condicionais

Encontre loops e condicionais

Passos para analisar um algoritmo e decidir os três casos

3. Decida quantas vezes o condicional irá executar baseado na quantidade de vezes que o loop executa.

*É preciso olhar para o condicional, pois o custo de acesso a memória vem dele!

Encontre loops e condicionaisSe tamanho = n, então o for executará n vezes, uma vez que vai de 0 até (n – 1).

Para visualizar o número de vezes que o for executa, pode-se fazer o seguinte:

Por exemplo, se n = 2, i começa em 0 (i = 0) e 0 < 2. Na segunda iteração, i recebe 1 (i = 1) e 1 < 2. A terceira iteração nos dá que i será igual a 2 (i = 2) e 2 < 2 é falso e o loop não será executado novamente. Logo, o loop executou somente 2 vezes, uma vez que a terceira

iteração não foi executada. Veja que 2 é o número de elementos que temos, pois n = 2 e então o loop rodou n vezes.

Passos para analisar um algoritmo e decidir os três casos

3. Seja f(n) uma função de complexidade, decida f(n) para o melhor e pior caso e caso médio, utilizando seu conhecimento sobre o problema.

Decida quantas vezes será executado

Melhor caso: 𝑓 𝑛 = 1

O if foi acessado somente uma vez, pois o elemento estava na primeira posição acessada.

Pior caso: 𝑓 𝑛 = 𝑛

O if foi acessado todas as vezes que o loop executou, pois o elemento procurado estava na última posição acessada ou não estava no vetor.

Seja 𝑓 𝑛 uma função de complexidade definida pelo número de elementos consultados no arquivo.

Decida quantas vezes será executado

Caso médio: 𝑓 𝑛 =𝑛+1

2

O caso médio é dado por:

𝑃𝑖𝑜𝑟 𝑐𝑎𝑠𝑜 + 𝑀𝑒𝑙ℎ𝑜𝑟 𝑐𝑎𝑠𝑜

2

É o mesmo que dizer que o elemento está no meio ou próximo dele!

Seja 𝑓 𝑛 uma função de complexidade definida pelo número de elementos consultados no arquivo.

Análise assintótica

Para a análise de algoritmos só vai importar mesmo, quando temos valores enormes de n. Isso é necessário, porque até mesmo o pior dos algoritmos pode resolver algum problema quando n é suficientemente pequeno.

Análise assintótica

O tipo de matemática que está interessado em valores enormes de n, é chamado de assintótico, e as funções aqui definidas serão classificadas em “ordens” (como as ordens religiosas da Idade Média), onde todas as funções de uma mesma ordem são equivalentes.

Análise assintótica

Por exemplo, sejam as funções:

n2 , (3/2)n2 , 9999n2 , n2/1000 , n2+100n , etc.

Elas crescem todas na mesma velocidade e portanto são todas “equivalentes” e desse modo de mesma “ordem”.

Análise assintótica

Por exemplo, sejam as funções:

n2 , (3/2)n2 , 9999n2 , n2/1000 , n2+100n , etc.

Nesse caso é fácil de perceber que todas crescem na mesma velocidade. Todas as funções dadas são quadráticas. Olhem para os gráficos á seguir:

Análise assintótica

As proporções são diferentes, mas as curvas tem o mesmo comportamento! (comportamento é o mesmo que dizer crescimento)

Aqui, vamos nos concentrar na primeira ordem, a Ordem O.

Dominação assintótica

Se pudermos provar que f(n) domina assintoticamente g(n) a partir de um ponto m quando n-> infinito, então o caso ao lado não pode ser verdadeiro!

A partir de agora, passaremos a representar os algoritmos através de funções de complexidade de variável n onde essa função é sempre maior que zero.

Para o nosso contexto, vamos definir que uma função f(n) domina assintoticamente outra função g(n) se quando n -> infinito, a curva de g(n) nunca crescerá mais rápido que a curva de f(n) a partir de um ponto m (n0).

Ordem O

Definição: Dadas funções assintoticamente não negativas f(n) e g(n), dizemos que g(n) está na ordem O de f(n) e escrevemos

para expressar que f(n) domina assintoticamente g(n). Isso significa dizer que se o tempo de execução de um programa fosse representado por g(n), ele seria da ordem de no máximo f(n).

Ordem O

Se afirmamos que então estamos dizendo que é

possível encontrar duas constantes positivas c e m tais que, para 𝑛 ≥ 𝑚 temos 𝑔 𝑛 ≤ 𝑐 ∗ |𝑓 𝑛 |.

No gráfico ao lado, f(n) só domina assintoticamente g(n) a partir de m e quando encontramos uma constante c apropriada!

Ordem O

Exemplo: Seja 𝑔 𝑛 = 𝑛 + 1 2 𝑒 𝑓 𝑛 = 𝑛2 podemos afirmar que 𝑔 𝑛 = 𝑂 𝑓 𝑛 ?

Pela definição isso será verdade quando

𝑛 + 1 2 ≤ 𝑐𝑛2 𝑝𝑎𝑟𝑎 𝑛 ≥ 𝑚

Cada problema tem uma forma mais prático que outro para encontrarmos a constante c. Para esse caso precisamosabrir g(n) ficando com:

𝑛2 + 2𝑛 + 1A estratégia aqui é igualar os graus em todos os elementos acima com f(n), que possui o maior grau quadrático (2). Logo, sabemos então que:

𝑛2 + 2𝑛 + 1 ≤ 𝑛2 + 2𝑛2 + 1𝑛2

Para algum 𝑛 ≥ 0 que ainda não sabemos qual é (esse será nosso m!)

Ordem O

Exemplo: Seja 𝑔 𝑛 = 𝑛 + 1 2 𝑒 𝑓 𝑛 = 𝑛2 podemos afirmar que 𝑔 𝑛 = 𝑂 𝑓 𝑛 ?

𝑛2 + 2𝑛 + 1 ≤ 𝑛2 + 2𝑛2 + 1𝑛2

Somando todos os termos do lado direito temos que:

𝑛2 + 2𝑛 + 1 ≤ 4𝑛2 (1)

Comparando com a nossa situação inicial:

𝑛 + 1 2 = 𝑛2 + 2𝑛 + 1 ≤ 𝑐𝑛2

Podemos perceber que c = 4. Vamos achar nosso m. Se n = 0, substituindo em (1):

1 ≤ 0 𝑜 𝑞𝑢𝑒 𝑛ã𝑜 é 𝑣𝑒𝑟𝑑𝑎𝑑𝑒!

Ordem O

Exemplo: Seja 𝑔 𝑛 = 𝑛 + 1 2 𝑒 𝑓 𝑛 = 𝑛2 podemos afirmar que 𝑔 𝑛 = 𝑂 𝑓 𝑛 ?

𝑛2 + 2𝑛 + 1 ≤ 𝑛2 + 2𝑛2 + 1𝑛2

Somando todos os termos do lado direito temos que:

𝑛2 + 2𝑛 + 1 ≤ 4𝑛2 (1)

Se n = 1, substituindo em (1):

4 ≤ 4 𝑜 𝑞𝑢𝑒 é 𝑣𝑒𝑟𝑑𝑎𝑑𝑒!

Como já determinamos nosso c, então o primeiro valor de n que torna a inequação verdadeira será o nosso n!

Ordem O

Exemplo: Seja 𝑔 𝑛 = 𝑛 + 1 2 𝑒 𝑓 𝑛 = 𝑛2 podemos afirmar que 𝑔 𝑛 = 𝑂 𝑓 𝑛 ?

Logo 𝑔 𝑛 = 𝑂 𝑓 𝑛 é uma afirmação válida quando definimos c = 4 e m = 1.

É importante notar que nem sempre se conseguiráresolver o problema utilizando esta abordagem e precisamos de outras estratégias para encontrar as duasconstantes que vão provar a nossa afirmação!

Perguntas?