Ao final do semestre, caso o aluno possua média final maior ou igual a 5, mas estiver bloqueado por um critério de barreira de aprovação (média das provas menor que 5), a prova substitutiva será considerada como prova delta. A nota da delta deve ser maior ou igual a 5 para a aprovação na disciplina. Caso contrário, o aluno estará reprovado na disciplina (mesmo que tiver média superior a 5).
Nessa disciplina iremos aprender a medir a eficiência de algoritmos, ou seja, calcular o tempo de execução do algoritmo.
A partir do tempo de execução do algoritmo é possível comparar algoritmos que resolvam um mesmo problema.
Para obter o tempo de execução de um algoritmo poderíamos implementar o algoritmo e realizar vários testes para várias entradas. Mas ai surge algumas questões:
O hardware (memória, processador, disco, etc..) influencia ?
E qual a influência do software (SO, linguagem de programação, compilador, código é intretado, etc ) ?
Nesse caso, você estaria comparando implementações, e não algoritmos.
Podemos abstrair o problema, ou seja, focar propriedades essenciais para calcular o tempo de execução, desconsiderando os detalhes de implementação que não são relevantes para o nível de análise realizado.
Em vez de perguntar
Perguntamos
C, Java ou `Python;O que importa é que o laço é executado aproximadamente n vezes.
Assim, modelamos o tempo de execução por uma função do tamanho da entrada, como:
onde:
Agora vamos contar aproximadamente as operações.
| Operação | Quantidade |
|---|---|
| 1 | |
| 1 | |
| n + 1 | |
| n | |
| n | |
| 1 |
Somando tudo:
ou
Na Análise de Algoritmos, a abstração consiste em ignorar os detalhes específicos da implementação — como linguagem de programação, compilador e hardware — e representar o custo de um algoritmo apenas em função do tamanho da entrada.
Essa abstração permite comparar algoritmos de maneira geral, utilizando funções matemáticas e notações assintóticas, como
Identificar e demonstrar a complexidade de espaço e tempo de algoritmos utilizando notação assintótica;
Projetar e implementar algoritmos utilizando divisão e conquista, programação dinâmica e estratégias gulosas;
Descrever as intuições e funcionamento de algoritmos no contexto de entrevistas técnicas de programação.
Uma entrevista técnica é um processo de avaliação em que o candidato deve demonstrar sua capacidade de resolver problemas, justificando suas escolhas e avaliando a eficiência das soluções utilizando conceitos como complexidade;
Normalmente utilizado no processo seletivo em empresas de tecnologia (Google, Microsoft, Amazon, Meta, Nubank, iFood, entre outras);
Exemplo de Problema: "Dado uma sequencia de números inteiros, determine a maior diferença absoluta entre dois elementos da sequência ?"
Entendimento do problema, caso não esteja claro faça perguntas para evitar ambiguidade;
Proponha uma solução, mesmo usando força-bruta;
Análise de solução e definição da complexidade da solução;
Propor melhorias na solução de forma a diminuir a complexidade;
A solução funciona para todos os casos;