AULA 02 - Projeto e Análise de Algoritmos - Resolução de Exercícios

Disciplina: Projeto e Análise de Algoritmos
AULA 02: Análise Assintótica - Resolução de Exercícios
Professor: Danilo Medeiros Eler
daniloeler.github.io/teaching...
Conteúdo:
- Análise de Algoritmos
- Análise Assintótica
- Complexidade de Tempo
- Classes de Comportamento Assintótico
- Notação Assintótica
Bacharelado em Ciência da Computação
Faculdade de Ciências e Tecnologia
Departamento de Matemática e Computação
Programa de Pós-graduação em Ciência da Computação
Unesp - Universidade Estadual Paulista
Presidente Prudente/SP, Brasil
#analisealgoritmos #projetoalgoritmos #analiseassintotica #assintotica #complexity #analysis #design #algorithms #analise #projeto #algoritmos #complexidade #assintotic #concursopetrobras #concurso #concursos #petrobras #computacao #cienciadacomputacao

[@alfamath3298]

Finalmente consegui entender essas notações. top

[@mikaelandrade5795]

Obrigado pelas aulas, estão me ajudando muito na matéria de PAA.

[@engso.arthur]

Isso sim é didática

[@hugovinicius2451]

Professor show de bola

[@wiltonribeiro9198]

Parabéns!

[@PauloViniciusMoreiraDutra]

O laço for não contaria? Por exemplo, na primeira questão, letra a: 1 + n + n. Ou seja, o n que coloquei a mais é do incremento da variável i. Essa é minha dúvida

[@danilome]

Pode contar tanto o incremento quanto a verificação (i

[@PauloViniciusMoreiraDutra]

@@danilome Muito obrigado professor. Excelente explicação em seus vídeos.

[@aanshirra8445]

na letra i) voce diz que as duas linhas de dentro do for serão executadas. só que é um if. existe a chance de que aquela atribuição "menor = menor[i]" nao seja executada

[@danilome]

Ola. Depende do caso. No pior caso as duas são executadas, ou seja, sempre troca o valor do menor. No melhor caso pode não ser executada ou ser executada só uma vez. Você tem que fazer as duas análises nesse exercício.

[@aanshirra8445]

@@danilome mas voce considerou ele no melhor caso. por isso a duvida

[@danilome]

​​​@@aanshirra8445indiquei que no melhor caso é executado uma vez. Só não seria executado se o vetor estivesse todo preenchido com 'MAIOR-INTEIRO'

[@aanshirra8445]

@@danilome mas o melhor nao seria nao executar nenhuma, nesse caso ?

[@danilome]

@@aanshirra8445 ola. O if sempre é executado, mas como você bem observou a instrução menor = vetor[i] pode não ser executada quando o vetor inteiro estiver preenchido com MAIOR-VALOR em todas as posições, mas isso é mais raro de ocorrer na pratica. Mas seria sim o melhor caso. Mas quando colamos na notação assintotica nao da diferença,pois é apenas uma constante

[@bentrieloniichan2607]

no caso na letra d) o custo não seria 1 no melhor caso? já que se não tiver nenhum nome ele entra no else direto e faz só uma operação.

[@danilome]

Ola. Na análise, consideramos um tamanho 'n', ou seja, sempre tem elementos para realizar a busca. Não podemos dizer que está vazio. Pois, se considerarmos zero elementos, todos os algoritmos teriam o mesmo tempo no melhor caso, isto é, nao seriam executados.